力扣---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

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

if (i > start && candidates[i] == candidates[i - 1]) continue;

这行代码目的就是排除在该循环中已经使用过的数值。

代码逻辑

• i > start：确保我们不会跳过第一个元素，因为第一个元素前面没有元素可以比较。
• candidates[i] == candidates[i - 1]：检查当前元素与前一个元素是否相同。

如果 candidates[i] 与 candidates[i - 1] 相同，并且 i > start，说明 candidates[i] 是本层递归中第一个使用 candidates[i-1] 后的重复元素，因此直接跳过 candidates[i] 以避免生成重复组合。

示例

对于 candidates = {1, 2, 2, 2, 3, 4, 5}，目标是 5。假设在某次递归中，当前 start 为 0：

• 第一次循环（i = 1），处理 2，递归调用继续。
• 第二次循环（i = 2），又遇到 2，因为 i > start 并且 candidates[i] == candidates[i - 1]，所以跳过这个 2，避免重复。
• 第三次循环（i = 3），再次遇到 2，同样跳过。

这样就避免了类似 [2, 2, 2, 3] 的重复组合，保证每个组合唯一。

时间超时

class Solution {
public:
    bool exist(vector<vector<int>>& ans, vector<int>& curr){
        int n = ans.size();
        int n_c = curr.size();
        int num = 0;
        for(int i=0;i<n;i++){
            if(n_c != ans[i].size()) {
                num++;
                continue;
            }
            for(int j=0;j<n_c;j++){
                if(curr[j]!=ans[i][j]){
                    num++;
                    break;
                }
            }
        }
        if(num == n)
            return false;
        else 
            return true;
    }
    void find_ans(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& curr, int start){
        if(target == 0){
            if(!exist(ans, curr)){
                ans.push_back(curr);
            }
            return;
        }
        for(int i=start;i<candidates.size();i++){
            if(candidates[i]>target) break;
            curr.push_back(candidates[i]);
            find_ans(candidates, target-candidates[i], ans, curr, i+1);
            curr.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> curr;
        find_ans(candidates, target, ans, curr, 0);
        return ans;
    }
};