Leetcode No.40 组合总和 II（DFS）

一、题目描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。

示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

二、解题思路：递归 + 回溯

由于我们需要求出所有和为 target 的组合，并且每个数只能使用一次，因此我们可以使用递归 + 回溯的方法来解决这个问题：

我们用dfs(pos,rest) 表示递归的函数，其中pos 表示我们当前递归到了数组 candidates 中的第pos 个数，而 rest 表示我们还需要选择和为rest 的数放入列表作为一个组合；

对于当前的第 pos 个数，我们有两种方法：选或者不选。如果我们选了这个数，那么我们调用dfs(pos+1,rest−candidates[pos]) 进行递归，注意这里必须满足 rest≥candidates[pos]。如果我们不选这个数，那么我们调用 dfs(pos+1,rest) 进行递归；

在某次递归开始前，如果 rest 的值为 0，说明我们找到了一个和为target 的组合，将其放入答案中。每次调用递归函数前，如果我们选了那个数，就需要将其放入列表的末尾，该列表中存储了我们选的所有数。在回溯时，如果我们选了那个数，就要将其从列表的末尾删除。

上述算法就是一个标准的递归 + 回溯算法，但是它并不适用于本题。这是因为题目描述中规定了解集不能包含重复的组合，而上述的算法中并没有去除重复的组合。

如何去掉重复的集合（重点） 为了使得解集不包含重复的组合。有以下 2 种方案：

1、使用 哈希表 天然的去重功能，但是编码相对复杂； 2、这里我们使用和第 39 题（组合之和）和第 15 题（三数之和）类似的思路：不重复就需要按 顺序 搜索， 在搜索的过程中检测分支是否会出现重复结果 。注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。

由第 39 题我们知道，数组 candidates 有序，也是 深度优先遍历 过程中实现「剪枝」的前提。 将数组先排序的思路来自于这个问题：去掉一个数组中重复的元素。很容易想到的方案是：先对数组 升序 排序，重复的元素一定不是排好序以后相同的连续数组区域的第 1 个元素。也就是说，剪枝发生在：同一层数值相同的结点第 2、3 ... 个结点，因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果，同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 1 个结点更多，并且是第 1个结点的子集。

三、代码

public class Solution2 {
    List<List<Integer>> rs=new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0) {
            return rs;
        }
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>(candidates.length);
        dfs(candidates,path,target,0);
        return rs;
    }
    void dfs(int[] candidates, Deque<Integer> path, int target, int index){
        if(target==0){
            rs.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
            if (target - candidates[i] < 0) {
                break;
            }
            // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
            if (i > index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.addLast(candidates[i]);
            System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
            // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
            dfs(candidates,path,target-candidates[i],i+1);
            path.removeLast();
            System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
        }
    }
    public static void main(String[] args) {
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        Solution2 solution = new Solution2();
        List<List<Integer>> res = solution.combinationSum2(candidates, target);
        System.out.println("输出 => " + res);
    }
}

四、复杂度分析

1、时间复杂度：O(2^n*n)

其中 n是数组candidates 的长度。在大部分递归 + 回溯的题目中，我们无法给出一个严格的渐进紧界，故这里只分析一个较为宽松的渐进上界。在最坏的情况下，数组中的每个数都不相同，那么列表 freq 的长度同样为 n。在递归时，每个位置可以选或不选，如果数组中所有数的和不超过 target，那么 2^n种组合都会被枚举到；target 小于数组中所有数的和时，我们并不能解析地算出满足题目要求的组合的数量，但我们知道每得到一个满足要求的组合，需要 O(n) 的时间将其放入答案中，因此我们将 O(2^n)与O(n) 相乘，即可估算出一个宽松的时间复杂度上界。 由于 O(2^n*n) 在渐进意义下大于排序的时间复杂度O(nlogn)，因此后者可以忽略不计。

2、空间复杂度：O(n)。

除了存储答案的数组外，我们需要O(n) 的空间存储列表freq、递归中存储当前选择的数的列表、以及递归需要的栈。