java算法day21

77 组合
216 组合总和Ⅲ
17 电话号码的数字组合
39 组合总和

这个阶段所要解决的问题都是有关回溯算法。
所以说解法基本上都是围绕回溯算法模板来完成。回溯算法可以这样总结，树形结构，横向遍历，纵向递归。递归出口收货结果并终止。本层递归处理完之后，对path恢复现场。

77 组合

上来将问题抽象为属性结构。就可以看到回溯的思路。
未优化思路：
在这里插入图片描述
按照这样的思路：
每一层所要做的就是遍历，取结果加入path路径之后就递归下层，收集下一个元素。可以这么理解，每层收集一个元素，所以说一定是要递归下去，加入元素是在不同的递归层，当path符合之后才进行收割结果。

class Solution {//全局变量，用于存结果List<List<Integer>> result= new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();//主方法public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1);return result;}//回溯算法public void backtracking(int n,int k,int startIndex){//递归出口，path符合条件，收割结果，返回上一层if (path.size() == k){result.add(new ArrayList<>(path));return;}//这里是本层的逻辑，对于本层来说，横向是做遍历，目的是开不同的分支//这里是从startIndex开始散开每个分支。//从模板而言，每一层都在做横向遍历，开枝散叶。for (int i =startIndex;i<=n;i++){//收集本层节点path.add(i);//递归下一层backtracking(n,k,i+1);//回来之后把上一层收集的元素，做弹出，就完成了恢复现场。path.removeLast();}}
}

优化逻辑：
也就是可以从已收集的元素个数，来判断出，如果索引走到某个位置之后，后面就不可能收集到结果。所以后面的路可以说是白走。所以这里就是把白走的路给剪掉。
在这里插入图片描述

举个例子
n = 4 k = 3
那么这里就很清楚，第一层，最多索引走到i = 2，这样能取到2，3，4这样的组合。后面的3，4就没必要去走。
根据这样的规律可以进行这个边界的计算：
比如从一开始，path还没收集元素
path.size()：已经收集到的元素个数。现在为0
k-path.size()还缺少的元素个数现在为3
现在看最多走到哪。
n-(k-path.size()) = 1。这显然不是最边界，还要+1。
所以目前i的极限取值就是i=n-(k-path.size())+1。对于本层i而言，最多取到这个位置，一旦超了，后面的路可以说是白走。

因此这个剪枝的特点是通过循环条件来完成的。

可以看到就改了循环条件

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return result;}/*** 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex* @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。*/private void combineHelper(int n, int k, int startIndex){//终止条件if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){path.add(i);combineHelper(n, k, i + 1);path.removeLast();}}
}

216 组合总和Ⅲ

这题和组合没太大差别，可以理解为就在以往收集结果的时候多加了一个判断条件，判断path中的元素值总和是否等于target。等于了才收集。

所以说由于是组合问题，所以起手还是抽象树形结构。横向遍历，纵向递归。
在这里插入图片描述
可以看到，就是在收集结果的时候多加了一个条件判断。

本题还有一些要注意的点，也就是把n锁死了，最多只到9，所以说写循环条件剪枝的时候n直接写9。
所以剪枝依然是同样的逻辑。而且还多了一个剪枝条件，一旦还没走到底，sum已经大于targetSum了，那后面没必要走，也返回。
在这里插入图片描述

接下来看代码：
剪枝版本：

class Solution {
//全局变量，用于存结果。List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();
//主函数public List<List<Integer>> combinationSum3(int k, int n) {backTracking(n, k, 1, 0);return result;}
//回溯private void backTracking(int targetSum, int k, int startIndex, int sum) {// 减枝1//值大于targetSum，后面没必要走，直接返回，不用担心负数，因为题目给的1-9if (sum > targetSum) {return;}//剪枝2。path满足大小，收割结果，然后返回，这里已经到叶子节点了。if (path.size() == k) {if (sum == targetSum) result.add(new ArrayList<>(path));return;}// 减枝 9 - (k - path.size()) + 1//还是先前的剪枝规则//横向遍历。for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {//收集path元素path.add(i);//累加节点值。sum += i;//递归下一层，i不能取当前，i要+1backTracking(targetSum, k, i + 1, sum);//回溯path.removeLast();//回溯，回溯的时候不仅把下层已收集的元素弹出，sum也要减去。sum -= i;}}
}

17 电话号码的数字组合

在这里插入图片描述
从图中应该可以感受出来，单个数字代表的元素，代表了横向遍历的长度。
输入的字符串长度，代表了纵向递归的深度。

class Solution {//设置全局列表存储最后的结果List<String> list = new ArrayList<>();//主函数，做特判。public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return list;}//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""//题目要求的映射，直接通过下标进行关联。String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//开始迭代处理backTracking(digits, numString, 0);//返回结果return list;}//每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder//又是一个全局变量。StringBuilder temp = new StringBuilder();//比如digits如果为"23",num 为0，则str表示2对应的 abcpublic void backTracking(String digits, String[] numString, int num) {//遍历全部一次记录一次得到的字符串//收割结果做剪枝，一旦收集到的元素等于输入的字符串的长度，就收集返回。if (num == digits.length()) {list.add(temp.toString());return;}//str 表示当前num对应的字符串，获取该数字映射的字符串。String str = numString[digits.charAt(num) - '0'];//取得了字符串，那么开始做横向遍历。对于1对应的abc而言，开始取a，取b，取c。从题目的意思，再根据这个树，就是这样的含义。for (int i = 0; i < str.length(); i++) {//取第一个元素加入temp中。temp.append(str.charAt(i));//递归，处理下一层，注意前面我强调的，进入下一层就是到另一个数字代表的字符串了。所以要num+1。标识处理digits的下一个元素。backTracking(digits, numString, num + 1);//剔除末尾的继续尝试，//这里就是回溯，把下层的元素弹出，恢复现场。temp.deleteCharAt(temp.length() - 1);}}
}

39 组合总和

这题和前面又有点不一样了，他不限制path.size()要满足多少了。
最主要就是符合targetSum。因此之前用的剪枝就不能套用一模一样的，需要改。

由题意，还是把树模型给抽象出来，题目中还说了，数组中的元素各不相同。而且同一个元素可以取多次，但注意，虽然一个元素可以取多次，但这并不意味着和排列一样。比如2，3 target = 7。如果你按排列的思想去想，那么这个题2，2，3和3，2，2有两个答案，但是题目说了，这是一个答案，个数是不能重复的，因此就算元素可以重复取，但是要求结果集中，元素组合不能完全相同。所以这本质还是组合问题，因此为了防止上述情况出现，那么我的树结构依然是这样，取过的元素就会枚举出该元素的所有可能，后面就不能再取了。

在这个过程中也可以看到剪枝，就是sum>=targetSum，那么就可以提前return了。从这个图来看，仍然是组合的思想。
在这里插入图片描述
那么有没有什么方法可以优化？回答是有的。

那么就是排序。因为这个题目你会发现，排序之后会发现这样的好处：
或许还是感觉不出排序有什么好处。这里来进行对比。
比如在[2,5,3,1]
先前这种递归，都是在递归下一层之后，通过if条件来进行判断，是否提前剪枝，这是发生在下一层。发生在下一层有什么坏处？那就是实际你多递归一层，那么就会多一层递归调用栈。那么如果我们想，能不能在上一层解决这样的递归。提前在上一层检查了，就不进入下一层了。

所以这里提出了排序的方法。
排序之后我们直接在本层做判断

看这个例子：
现在如果排序了是1，2，3，5
上来就先做判断，要不要去下一层了，而且这里还有一个精髓if (sum + candidates[i] > target) break;这里可以一并砍掉横向遍历没必要的循环。因为是排序过了的，后面不可能的序列不可能再存在解。

也许你会这样想，对于没排序过的，也做了这样的剪枝，会发生什么。
在2，5，3，1中。target=4。这样显然会在5之后会把后面的横向遍历3，1给砍掉。漏结果了。

for (int i = idx; i < candidates.length; i++) {// 如果 sum + candidates[i] > target 就终止遍历if (sum + candidates[i] > target) break;path.add(candidates[i]);backtracking(res, path, candidates, target, sum + candidates[i], i);path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素}

在这里插入图片描述

不排序+剪枝
也是减少递归调用栈。我个人推荐写这种。这种只是优化了函数调用栈。
由于不是排序，所以大的元素后面，也是有可能存在小的元素，因此存在解。所以顶多只能跳过这个大的。不去扩展他的下层。

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();// Arrays.sort(candidates); // 先进行排序backtracking(res, new ArrayList<>(), candidates, target, 0, 0);return res;}public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {// 找到了数字和为 target 的组合if (sum == target) {res.add(new ArrayList<>(path));return;}//注意递归下一层index还是i，因为元素是可以重复取得。for (int i = idx; i < candidates.length; i++) {// 如果 sum + candidates[i] > target 就终止遍历//直接在本层就做了剪枝，不去判断下一层。if (sum + candidates[i] > target) continue;path.add(candidates[i]);backtracking(res, path, candidates, target, sum + candidates[i], i);path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素}}
}

排序+剪枝
排序之后可以帮我们少走很多路。
大于后的数字直接就砍掉了。

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(candidates); // 先进行排序backtracking(res, new ArrayList<>(), candidates, target, 0, 0);return res;}public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {// 找到了数字和为 target 的组合if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = idx; i < candidates.length; i++) {// 如果 sum + candidates[i] > target 就终止遍历if (sum + candidates[i] > target) break;path.add(candidates[i]);backtracking(res, path, candidates, target, sum + candidates[i], i);path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素}}
}