组合问题

为什么要用回溯？

组合题：已知一个集合1,2,3,4，要求将大小为2的集合找出来，两层for很容易得出，但是100个数50个集合呢，如何通过一个数k来控制for循环的层数呢

回溯算法就是递归来控制有多少层for循环

这类题就是把树形结构给想好，套模板即可解决

题目：77. 组合

77. 组合

class Solution {LinkedList<Integer> path = new LinkedList<>();//用LinkedList是细节List<List<Integer>> result = new ArrayList<>();//可以放到递归函数的参数列表中，但为了提升代码可读性，所以放在类属性里面public List<List<Integer>> combine(int n, int k) {backtracking(n, k, 1);return result;}void backtracking(int n, int k, int startIndex) {if(path.size() == k) {result.add(new ArrayList<>(path));return;}for(int i = startIndex; i <= n; i++) {path.add(i);backtracking(n, k, i + 1);path.removeLast();}return;}
}

优化（减枝操作）

来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

path.size();//已经有的元素个数
k-path.size();//还需要选取的元素个数
this = n-(k - path.size()) + 1;//至多从这里this开始搜索符合条件，如果当前i在this之后就一定不符合条件了,因为i是从startIndex开始包含startIndex，所以需要加1；startIndex到n总共有n-startIndex+1个数,我思考的是右半部分的大小
//为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合[1,2,3,4]

回溯算法如果想要剪枝，就思考for的范围是不是太大了

class Solution {LinkedList<Integer> path = new LinkedList<>();//用LinkedList是细节List<List<Integer>> result = new ArrayList<>();//可以放到递归函数的参数列表中，但为了提升代码可读性，所以放在类属性里面public List<List<Integer>> combine(int n, int k) {backtracking(n, k, 1);return result;}void backtracking(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);backtracking(n, k, i + 1);path.removeLast();}return;}
}

限定条件组合 题目：216. 组合总和 III

216. 组合总和 III

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k, n, 1, 0);return result;}void backtracking(int k, int n, int startIndex, int sum) {//有多少限制条件，就该有多少剪枝操作if(sum > n) return;//剪枝,关于和n的if(path.size() == k) {//如果数量够了就没必要往下递归了if(sum == n ) {//符合条件result.add(new ArrayList<>(path));}return;}for(int i = startIndex; i <= 9 - (k -path.size()) + 1; i++) {//组合剪枝：集合.size - (所需数量 - 已经收集.size) + 1path.add(i);backtracking(k, n, i + 1, sum + i);path.removeLast();}}
}

上面的终止条件path.size()k和sumn这一点若同时在同一个if中，会一直循环stackoverflow;

若每次循环的集合不一致 ：17. 电话号码的字母组合

17. 电话号码的字母组合

class Solution {//设置全局列表存储最后的结果List<String> result = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0) {return result;}String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};backtracking(digits, 0, numString);return result;}public void backtracking(String digits, int index, String[] numString) {//numString是映射数组//设置终止条件：遍历到叶子节点就结束了，也就是说给的字符串遍历完了if(index == digits.length()) {result.add(sb.toString());return;}//得到循环处理用的字符串String s = numString[digits.charAt(index) - '0'];for(int i = 0; i < s.length(); i++) {sb.append(s.charAt(i));backtracking(digits, index + 1, numString);sb.deleteCharAt(sb.length() - 1);}}
}

若元素可重复选取 ：39. 组合总和

39. 组合总和

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates, target, 0, 0);return result;}void backtracking(int[] nums, int target, int sum, int startIndex) {// 两个终止条件//值大于目标值if(sum > target) {return;}//找到目的pathif(sum == target) {result.add(new ArrayList<>(path));return;}for(int i = startIndex; i < nums.length; i++) {//横向遍历//剪枝，对于排完序的数组，如果我的和已经大于了目标值，那么我后面的层序遍历和下面的纵向遍历都没有必要了if((sum + nums[i]) > target) break;path.add(nums[i]);backtracking(nums, target, sum + nums[i], i);path.removeLast();}}
}

集合中有重复的元素：40. 组合总和 II

40. 组合总和 II

本题集合中有重复的元素，也就是说要进行去重

所有回溯问题都可以抽象成一颗n叉树，想想在n叉树中是怎么去重的–选到重复的元素有两种情况，一种是纵向遍历（树枝也就是一条分支即递归）另一种是横向遍历（树层也就是for循环），对于一个有序数组来说，我们要去重的是树层，因为树枝是纵向来说的，我们选了一个1，递归到下一层如果元素中有1，我们就还能选，但是如果在树层，例如集合[1,1,2,3]，遍历到下一个分支，第一次我们选了第二个1，由于前面已经有1了，在上一分支中，第一次选第一个1的时候已经包含了第二次选1的所有分支，甚至连第二个1自己都包含在内，就是说这层的这个分支没有必要存在了，反应在代码中就是在树层中（for循环中），如果前一个数字和本数字一致且上一个数字没用过，就说明本层本分支结束，对于树枝是没必要的，就是上一个数字用过了，那么就是说本循环是在第一个数字1的分支下面，不用去重。

class Solution {List<List<Integer>> result = new ArrayList<>();//记录结果LinkedList<Integer> path = new LinkedList<>();//记录单条分支public List<List<Integer>> combinationSum2(int[] candidates, int target) {//采用标记数组去重一定要记得将数组排序Arrays.sort(candidates);backtracking(candidates, target, 0, 0, new boolean[candidates.length]);return result;}void backtracking(int[] nums, int target, int sum, int startIndex, boolean[] used) {if(sum > target) {//已经大于目标值，本条分支不符合了return;}if(sum == target) {result.add(new ArrayList<>(path));}//回溯逻辑for(int i = startIndex; i < nums.length; i++) {//进行去重操作if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {//树层方面去重continue;}//一般处理逻辑path.add(nums[i]);used[i] = true;backtracking(nums, target, sum + nums[i], i + 1, used);used[i] = false;path.removeLast();}}
}