【39】组合总和

1. 题目描述

2. 题目链接

https://leetcode.cn/problems/combination-sum/

3. 思路

对于这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。

• 我们定义递归函数表示当前在数组的第位，还剩要组合，已经组合的列表为。

• 递归的终止条件为或者数组被全部用完。

• 在当前的函数中，每次我们可以选择跳过不用第个数，即执行。也可以选择使用第个数，即执行，注意这里必须满足。由于每个数字可以被无限制重复选取，因此搜索的下标仍为。

如果我们将整个搜索过程用一个树来表达，即如下图呈现，每次的搜索都会延伸出两个分叉（选择当前元素或不选择当前元素），直到递归的终止条件，这样我们就能不重复且不遗漏地找到所有可行解：

4. 代码实现

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates == null || candidates.length == 0) {
        return new ArrayList<>();
    }
    List<List<Integer>> ans = new ArrayList<>();
    dfs(target, new ArrayList<>(), 0, candidates, ans);
    return ans;
}
private void dfs(int target, List<Integer> combine, int idx, int[] candidates, List<List<Integer>> ans) {
    // 满足条件
    if (target == 0) {
        ans.add(new ArrayList<>(combine));
        return;
    }
    if (idx >= candidates.length) {
        return;
    }
    // 选择当前数字
    if (target - candidates[idx] >= 0) {
        combine.add(candidates[idx]);
        dfs(target - candidates[idx], combine, idx, candidates, ans);
        // 回溯
        combine.remove(combine.size() - 1);
    }
    // 跳过当前数字
    dfs(target, combine, idx + 1, candidates, ans);
}

• 时间复杂度：，其中为所有可行解的长度之和。从搜索树中可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在本题中，我们很难给出一个比较紧的上界，我们知道是一个比较松的上界，即个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但实际运行时，因为不可能所有的解都满足条件，且递归时还会用进行剪枝，所以实际运行情况是远小于这个上界的。

• 空间复杂度：。空间复杂度取决于递归的栈深度，由于数组中的元素最小为，因此在最差情况下需要递归层。

  【40】组合总和Ⅱ

  1. 题目描述

  

  2. 题目链接

  https://leetcode.cn/problems/combination-sum-ii/

  3. 思路

  这道题与第 39 题的区别在于：

• 第 39 题：中的数字可以无限制重复被选取；

• 第 40 题：中的每个数字在每个组合中只能使用一次，且包含重复元素。

因此，第 39 题的思路并不适用于本题。这是因为题目描述中规定了解集不能包含重复的组合，而上述的算法中并没有去除重复的组合。例如当，时，上述算法会将列表放入答案两次。因此，我们需要改进上述算法，在求出组合的过程中就进行去重的操作。

如何去掉重复的集合？
所谓去重，其实就是使用过的元素不能重复选取。 我们知道组合问题可以抽象为树形结构，那么「使用过」在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。由于题目要求元素在同一个组合内是可以重复的，但两个组合之间不能相同。所以，我们要去重的是同一树层上的「使用过」，同一树枝上的都是一个组合里的元素，因此不用去重。

要对树层去重，需要先对数组做升序排序，这样重复的元素一定不是排好序以后相同的连续数组区域的第个元素。即剪枝发生在：同一树层中，数值相同的节点中，第个结点，因为数值相同的第个节点已经搜索出了包含了这个数值的全部结果，那么数值相同的节点就不用再搜索了。

4. 代码实现

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    if (candidates == null || candidates.length == 0) {
        return new ArrayList<>();
    }
    List<List<Integer>> ans = new ArrayList<>();
    // 排序
    Arrays.sort(candidates);
    dfs(target, new ArrayList<>(), 0, candidates, ans);
    return ans;
}
private void dfs(int target, List<Integer> combine, int idx, int[] candidates, List<List<Integer>> ans) {
    // 满足条件
    if (target == 0) {
        ans.add(new ArrayList<>(combine));
        return;
    }
    for (int i = idx; i < candidates.length; i++) {
        // 大剪枝，因为candidates数组是顺序的，如果当前已经不满足了，则直接break
        if (target - candidates[i] < 0) {
            break;
        }
        // 小剪枝：跳过同一树层数值相同的元素
        if (i > idx && candidates[i] == candidates[i - 1]) {
            continue;
        }
        combine.add(candidates[i]);
        // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
        dfs(target - candidates[i], combine, i + 1, candidates, ans);
        combine.remove(combine.size() - 1);
    }
}

这里重点解释下：i > idx && candidates[i] == candidates[i - 1] 是如何避免重复的。这个方法最重要的作用是能够让同一层级不出现相同的元素。即：

      1
     / \
    2   2
   /     \
  5       5

这种情况不会发生，但是却允许了不同层级之间的重复。即：

    1
   /
  2
 /
2

这种情况确是允许的。那它是怎么做到的呢？

首先是用于判定当前元素是否和前一个元素相同的语句，但它没有判断是同一树层中的元素重复，还是同一树枝中的元素重复。因此，它无法允许第二个例子里的情况，因为当例二中第二个出现时，它就和上一个相同了。

为了只过滤同一树层中的相同元素，那么就要用来保证，因为在一个 for 循环中，所有被遍历到的数都是属于同一个树层的。我们要让一个树层中只出现一个，那么就放过第一个出现重复的，但不放过后面出现的。第一个出现的就是，第二个出现的就是。

如下示例为：candidates = [1, 2, 2, 5]，target = 8，层级结构如下图所示：

从图中可以看到，在纵向遍历的过程中，始终有（因为递归的入参中为，隐含地选择了下一个元素），而在 for 循环横向遍历的过程中是递增的，因此同一树层中，从第二个元素开始，始终有。