如何从 vector<vector<int>> 中删除重复项

Question

我正在尝试解决 Combination II 这类似于具有独特组合且没有无限重复硬币的硬币找零问题。

例如：coins: {1,2,4}, amount = 3 {1,1,1,1} 或 {1,1,2} 不允许，因为硬币 1 的频率是一次。（一枚硬币只能使用一次）

{1,1,4},amount=3 {1,1,2} --> 将被允许，因为这两个来自两个不同的 1 硬币。

工作代码： https://ide.geeksforgeeks.org/5fjEmsWXUr

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] = {{}};
        //traverse throuugh coins
        for (int i=0; i<candidates.size()-1; i++){
            // traverse through DP (amount -> 0 inclusive)
            for(int j = target; j>=candidates[i]; j--){ // just reverse it start with target and use target-coin amount to fill. In this way we are just adding current number not repeating the same no. infinite times as done in j = candidates[i] to target+1; 
                // order repetition will be there. 
                for(auto v: dp[j-candidates[i]]){
                    v.push_back(candidates[i]);                    
                    dp[j].push_back(v);
                } 
            }
        }
        return dp[target];        
    }
};

您的输入

[10,1,2,7,6,1,5]
8

输出

[[1,2,5],[1,2,5],[1,1,6],[2,6],[1,7],[1,7]]

预计

[[1,1,6],[1,2,5],[1,7],[2,6]]

就我而言：

[1,2,5] 出现了两次，[1,7] 也出现了。

我想删除这些重复项。 我知道我们可以使用 set 来存储它们。但是我在使用 set 和修改函数 return 类型时遇到问题。

Answer 1

使用 std::set。它实际上只是将内部 vector 替换为 set:

class Solution {
public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {

        std::sort(candidates.begin(), candidates.end());
        std::vector<std::set<std::vector<int>>> dp(target+1);
        dp[0] = {{}};
        //traverse throuugh coins
        for (int i=0; i<candidates.size()-1; i++){
            // traverse through DP (amount -> 0 inclusive)
            for(int j = target; j>=candidates[i]; j--){ // just reverse it start with target and use target-coin amount to fill. In this way we are just adding current number not repeating the same no. infinite times as done in j = candidates[i] to target+1; 
                // order repetition will be there. 
                for(auto v: dp[j-candidates[i]]){
                    v.push_back(candidates[i]);                    
                    dp[j].insert(v);
                } 
            }
        }
        return {dp[target].begin(),dp[target].end()};        
    }
};

只有在返回向量的向量时才需要变换集合，set没有push_back，而是insert.

如何从 vector<vector<int>> 中删除重复项

How to remove duplicate items from vector<vector<int>>

c++

c++14