如何移除vector<vector<int>>中重复元素以解决LeetCode Combination Sum II问题

问题原因 #

你当前代码的问题来自两个部分：

• 基础遍历错误：候选数组遍历的循环条件写为i < candidates.size()-1，会直接漏掉最后一个元素，导致部分组合无法生成
• 重复元素导致重复组合：排序后的候选数组存在连续相同值的元素时，相同值的元素会各自生成完全一致的组合，最终输出重复

方案1：Set去重实现（适配原有逻辑） #

不需要修改函数返回类型，仅需在返回前对结果去重即可，修改后代码如下：

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<vector<int>>> dp(target + 1);
        dp[0] = {{}};
        // 修复遍历边界错误
        for (int i = 0; i < candidates.size(); i++) {
            for (int j = target; j >= candidates[i]; j--) {
                for (auto v : dp[j - candidates[i]]) {
                    v.push_back(candidates[i]);                    
                    dp[j].push_back(v);
                } 
            }
        }
        // 利用set去重
        set<vector<int>> s(dp[target].begin(), dp[target].end());
        return vector<vector<int>>(s.begin(), s.end());
    }
};

方案2：优化DP逻辑（从根源避免重复，性能更优） #

通过跳过连续相同元素的方式，避免生成重复组合，无需额外去重步骤：

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<vector<int>>> dp(target + 1);
        dp[0] = {{}};
        int n = candidates.size();
        for (int i = 0; i < n; ) {
            int cnt = 0;
            // 统计当前相同值的元素个数
            while (i + cnt < n && candidates[i + cnt] == candidates[i]) cnt++;
            int num = candidates[i];
            // 逆序遍历dp
            for (int j = target; j >= num; j--) {
                // 最多用cnt个当前元素
                for (int k = 1; k <= cnt && j >= k * num; k++) {
                    for (auto v : dp[j - k * num]) {
                        // 添加k个当前元素
                        for (int t = 0; t < k; t++) v.push_back(num);
                        dp[j].push_back(v);
                    }
                }
            }
            // 跳过所有相同元素
            i += cnt;
        }
        return dp[target];
    }
};

验证结果 #

测试输入：
candidates = [10,1,2,7,6,1,5], target = 8
两种方案都可以得到预期输出：
[[1,1,6],[1,2,5],[1,7],[2,6]]

内容的提问来源于stack exchange，提问作者Pygirl