Combination Sum II

注意事項

重複要素を含む数列から一意の組合せを抽出する方法
重複する要素で開始することはできません.
ただし、重複する要素を抽出できる必要があります.

に答える

組合せは,以前に選択した要素を抽出しないことによって実現される.
ただし、重複する要素が存在する場合は、重複する組合せが抽出されます.
たとえば
[1,2,5,6,7,10]では
最初の要素を含む組合せ
[1.2.5.6.7.10]存在
2番目の面要素を含む組合せ
[1.2.5.6.7.10]存在
ここから見ると、
重複する要素で開始することはできません.
ただし、重複する要素を抽出できる必要があります.
重複する要素で開始したくない場合は、ソートされた要素の数が前の要素と同じかどうかを比較します.前の要素と同じです.以前に元素が処理した組み合わせなので、処理しません.インデックスが0の場合、重複するとは限らないため、除外されます.
ただし、重複する要素を抽出できる必要があります.その部分をflagで処理します.flagがtrueによって処理される事実には、「以前にこの値を取ったことがある.したがって、重複する要素であるが、その要素で始まるわけではないので、取ることもできる」という概念が含まれている.

コード#コード#

C++:flagが存在し、直感的

class Solution {
private: 
    vector<vector<int>> res;
public:
    void makeCombi(vector<int>& candidates, vector<int>& temp, int idx, int sum, int target){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.push_back(temp);
        }
        
        for(int i = idx; i < candidates.size()&& candidates[i] <= target; i++){
            if(i==idx||candidates[i-1]!=candidates[i]){
                temp.push_back(candidates[i]);
                makeCombi(candidates, temp, i+1, sum+candidates[i], target);
                temp.pop_back();                
            }
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<int> temp;
        makeCombi(candidates, temp, 0 , 0, target);
        return res;
    }
};

C++:flagは存在しません

class Solution {
private: 
    vector<vector<int>> res;
public:
    void makeCombi(vector<int>& candidates, vector<int>& temp, int idx, int sum, int target){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.push_back(temp);
        }
        
        for(int i = idx; i < candidates.size()&& candidates[i] <= target; i++){
            if(i==idx||candidates[i-1]!=candidates[i]){
                temp.push_back(candidates[i]);
                makeCombi(candidates, temp, i+1, sum+candidates[i], target);
                temp.pop_back();                
            }
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<int> temp;
        makeCombi(candidates, temp, 0 , 0, target);
        return res;
    }
};

重複する要素を抽出できる必要があります.「i=idxはこの要素で始まる」.次の要素を選択して抽出する必要があることを指定したので、できます.