40. 组合总和 II

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

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

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

回溯+排序，和为指定值的长度不限的可重不可复选组合问题

和为指定值的长度不限的可重不可复选组合问题。 先排序，让相同的元素靠在一起。base caee：和为目标和或者超过目标和。因为有重复数字，所以为避免产生重复组合结果， 所以先排序，然后在当前值等于前一个值时直接跳过。因为不可复选，所以子递归的起点需要加一。 回溯参数：数组，起点，目标值。一个列表存路径，一个列表存所有有效的路径。一个变量存路径和。

可重不可复选组合：本轮去重。

可重不可复选排列：全局去重，因为下次递归是从头开始。

trackSum既可以被设置为全局变量也可以被设置为回溯函数的参数。

就以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。

按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：

[ 
    [],
    [1],[2],[2'],
    [1,2],[1,2'],[2,2'],
    [1,2,2']
]

所以我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：

体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    List<Integer> track = new LinkedList<>();
    // 记录 track 中的元素之和
    // trackSum既可以被设置为全局变量也可以被设置为回溯函数的参数。
    int trackSum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0) {
            return res;
        }
        // 先排序，让相同的元素靠在一起。重点。
        Arrays.sort(candidates);
        backtrack(candidates, 0, target);
        return res;
    }

    // 回溯算法主函数，每层递归的选择空间为nums[start...n-1]
    void backtrack(int[] nums, int start, int target) {
        // base case，达到目标和，找到符合条件的组合
        if (trackSum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        // base case，超过目标和，直接结束。重点。不连续，有可能直接超过目标和
        if (trackSum > target) {
            return;
        }

        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 剪枝逻辑，值相同的树枝，只遍历第一条，不可复选，横向去重，纵向可重。
            // 如果nums中无重，则不需要剪枝，因为每次递归都从下一个元素开始。
            // 排列问题需要纵向去重，因为每次都从头开始遍历。纵向去重就是避免路径中出现重复元素，使用全局used数组+回溯实现。
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // 做选择，通过修改变量的状态完成。
            track.add(nums[i]);
            trackSum += nums[i];
            // 递归遍历下一层回溯树
            backtrack(nums, i + 1, target);
            // 撤销选择，即恢复变量的状态。
            track.removeLast();
            trackSum -= nums[i];
        }
    }
}

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