leetcode 40. 组合总和 II

题目

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

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

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

原题链接：https://leetcode.cn/problems/combination-sum-ii/description/

思路

dfs回溯。先对 candidates 进行排序。每次选定一个数字，然后 target 减去该数字，接着继续dfs。直到找到下一个数字刚好等于剩余target，此时刚好找到一种组合；如果下一个数字大于剩余target，则直接返回。
排序主要是为了方便剪枝。作用体现在两方面：

1. 当 下一个数字大于剩余target时，再下一个数字也一定大于剩余target。
2. 假如当前数字之前被选过了，即不是第一次选该数字，则也可以提前剪枝，避免重复组合。

• 复杂度分析
  • 时间复杂度 O(2^n)。每个数字都有选或不选的可能。
  • 空间复杂度 O(n)。空间复杂度取决于递归的栈深度。

代码

class Solution {
public:
    vector<vector<int>> result;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> temp;
        backtrace(candidates, temp, 0, target);
        return result;
    }
    void backtrace(vector<int>& candidates, vector<int>& temp, int start, int target) {
        if (target == 0) {
            result.push_back(temp);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                break;
            }
            temp.push_back(candidates[i]);
            backtrace(candidates, temp, i + 1, target - candidates[i]);
            temp.pop_back();
        }
    }
};