回溯 - 组合问题 - 《LeetCode题目总结》

组合问题概述

组合问题的两个关键点「备选集合中有无重复元素」和「备选集合中元素是否可以重复选取」，最终的答案都需要不包含重复的组合

无重复元素，不可重复选取
- 最简单的组合问题，需要一个startIndex来控制不重复选，不重复有两重含义
  - 组合的第一个元素不能跟其他的元素重复，也就是最终答案不能有重复的组合—->当前层 i从 startIndex开始遍历
  - 组合之内的元素不能重复，也就是任意一个组合内部不能有重复元素—->下一层 startIndex 应该i+1，即下一层i从i+1开始选
- 剪枝优化：可能是当前和加上选择的和大于目标值就剪枝（需要排序）、或者剩下的元素不足目标集合元素数量就剪枝
无重复元素，可以重复选取
- 可以重复选，说明，组合内部可以有重复元素，但是最终的答案不能有重复的组合，因此仍然需要一个startIndex
  - 组合的第一个元素不能跟其他的元素重复，也就是最终答案不能有重复的组合—->当前层i 从 startIndex开始遍历
  - 组合之内的元素可以重复，也就是当前元素可以被重复选择—->下一层 startIndex 应该为i，即下一层 i 还是从 i 开始选
- 剪枝优化：可能是当前和加上选择的和大于目标值就剪枝（需要排序）
有重复元素，不可重复选取
- 需要一个startIndex来控制不重复选，不重复有两重含义
  - 组合的第一个元素不能跟其他的元素重复，也就是最终答案不能有重复的组合—->当前层 i从 startIndex开始遍历
  - 组合之内的元素不能重复，也就是任意一个组合内部不能有重复元素—->下一层 startIndex 应该i+1，即下一层i从i+1开始选
- 还需要一个boolean[] used数组，来看是否使用过，备选数组要先排序，在备选数组元素相同的情况下
  - used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  - used[i - 1] == false，说明同一树层candidates[i - 1]使用过
有重复元素，可以重复选取
- 有重复元素，又可以重复选取，重复元素相当于没有，因为重复元素就是重复选取的结果，因此这种题目可以转化为「无重复元素，可以重复选取」问题
  77. 组合
递归函数的返回值以及参数

在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
其实不定义这两个全局遍历也是可以的，把这两个变量放进递归函数的参数里，但函数里参数太多影响可读性，所以我定义全局变量了。
函数里一定有两个参数，既然是集合n里面取k的数，那么n和k是两个int型的参数。
然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。
为什么要有这个startIndex呢？
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。
从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。

因此这部分的代码如下

List<Integer<Integer>> res ;
List<Integer> path;
void backtracking(int n, int k, int startIndex)

回溯的终止条件

什么时候到达所谓的叶子节点了呢？
path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
如图红色部分：

此时用result二维数组，把path保存起来，并终止本层递归。
所以终止条件代码如下：
注意这里的错误问题，java的函数调用是值传递，也就是传递了path的地址，因此整个代码共用了一个path变量，忘res里添加的都是一个path，最后的结果是res里的list都是一样的，且是空的，因为回溯的最后，path里没有元素。所以正确的写法应该是**res.add(new ArrayList<>(path));**

if(path.size() == k){
    res.add(path);//这里错了
    return ;
}

单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

如此我们才遍历完图中的这棵树。
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
代码如下：
注意这里的错误问题，下一层的startIndex取决于i，而不是当前层的startIndex，因为层数是深入的，不能重复选取有两个含义：一是集合的第一个元素无法选择大集合之前选过的元素—>参数中需要有startIndex，for循环从idx开始；二是集合后面的元素不能选择集合已经选过的元素—>下一层的startIndex = i + 1，下一层从之后开始选。

for (int i = startIndex; i <= n; ++i) {
    path.add(i);
    backtracking(n, k, startIndex + 1);//这里错了
    path.remove(path.size() - 1);
}

剪枝优化

举个例子，当 n = 4，k = 4 时，那么第一层for循环的时候，其实从2开始的遍历已经没有意义了，因为从2开始最多能选择3个元素，不足4个，因此根本就不用进回溯函数。同理，第二层for，从3开始的遍历已经没有了意义，如图所示

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。注意代码中 i，就是for循环里选择的起始位置
for (int i = startIndex; i <= n; ++i)
当前已经选择的元素个数：path.size()
还需要选择的元素个数：k - path.size()
因此 i 能取的最大值为：**n - (k - path.size()) + 1**
因此for循环修改为
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    void backtracking(int n, int k, int startIndex){
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return ;
        }
        for (int i = startIndex; i <= n; ++i) {
            path.add(i);
            backtracking(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
}

216. 组合总和 III

「组合元素数量固定，元素不可重复取，无重复元素，回溯结束条件略有区别」

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        res.clear();
        path.clear();
        backtrack(k, n, 1);
        return res;
    }

    public void backtrack(int k, int n, int startIndex){
        if (sum > n) { //剪枝
            return ;
        }
        if (path.size() == k) {
            if (sum == n) {
                res.add(new ArrayList<>(path));
            }
            return ;
        }
        //剪枝
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; ++i) {
            path.add(i);
            sum += i;
            backtrack(k, n, i + 1);
            sum -= i;
            path.remove(path.size() - 1);
        }
    }
}

17. 电话号码的字母组合

「每层能够选择的元素略有区别」

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    String[] phone = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return res;
        }
        backtrack(digits, 0);
        return res;
    }

    public void backtrack(String digits, int index){
        if (path.length() == digits.length()) {
            res.add(new String(path));
            return ;
        }
        String chars = phone[digits.charAt(index) - '0'];
        for (int i = 0; i < chars.length(); ++i) {
            path.append(chars.charAt(i));
            backtrack(digits, index + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

9. 组合总和

「组合元素没有数量要求，元素可无限重复选取，无重复元素」

剪枝优化

当sum > target的时候，我们已经进入了回溯函数，只是判断如果满足条件就返回，实际上我们不需要进入这一层的回溯函数，因此我们在进入回溯前的for循环中，就进行判断，当前的sum + candidates[i]是否已经大于target了，如果大于不进回溯，如果使用continue，还是要多次判断，如何判断一次sum + candidates[i]和target的关系就直接跳出循环break？所以要对candidates排序，如果sum + candidates[i]都比target大了，那么之后的值再加上肯定更大，直接跳出循环即可。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//剪枝关键
        backtrack(candidates, target, 0);
        return res;
    }

    public void backtrack(int[] candidates, int target, int startIndex){
        if (sum >= target) {
            if (sum == target) {
                res.add(new ArrayList<>(path));
            }
            return ;
        }
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; ++i) {
            path.add(candidates[i]);
            sum += candidates[i];
            backtrack(candidates, target, i); //这里从i开始，可以重复选
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

40. 组合总和 II

「组合元素没有数量要求，元素只能选择一次，有重复元素」
这道题目和 39.组合总和如下区别：

本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，而组合总和是无重复元素的数组candidates

最后本题和组合总和要求一样，解集不能包含重复的组合。
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！
所以要在搜索的过程中就去掉重复组合。
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）

回溯参数与返回值
递归终止条件
单层循环逻辑

要去重的是“同一树层上的使用过”，如果判断同一树层上元素（相同的元素）是否使用过了呢。
如果**candidates[i] == candidates[i - 1] **并且 **used[i - 1] == false**，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。
此时for循环中就应该continue
我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过

used[i - 1] == false，说明同一树层candidates[i - 1]使用过

class Solution {
  List<List<Integer>> res = new ArrayList<>();
  List<Integer> path = new ArrayList<>();
  int sum = 0;
  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      backtrack(candidates, target, 0, new boolean[candidates.length]);
      return res;
  }

  public void backtrack(int[] candidates, int target, int startIndex, boolean[] used){
      if (sum >= target) {
          if (sum == target) {
              res.add(new ArrayList<>(path));
          }
          return ;
      }
      for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; ++i) {
          if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
              continue;
          }
          path.add(candidates[i]);
          sum += candidates[i];
          used[i] = true;
          backtrack(candidates, target, i + 1, used);
          used[i] = false;
          sum -= candidates[i];
          path.remove(path.size() - 1);
      }
  }
}

组合问题

组合问题概述

77. 组合

216. 组合总和 III

17. 电话号码的字母组合

9. 组合总和

40. 组合总和 II