Combination Sum II

유의할점

중복된 원소가 포함된 수열에서 유일한 조합을 뽑는법

중복된 원소로 시작해서는 안된다.

하지만 중복된 원소를 뽑을수는 있어야한다.

풀이

조합은 이전에 선택했던 원소를 뽑지 않으면 이루어진다.

하지만 중복된 원소가 존재할경우 중복된 조합을 뽑게된다.

예를 들면

[1, 1, 2, 5, 6, 7, 10] 에서

첫번째 원소를 포함하는 조합중에

[1, 2, 5, 6, 7, 10] 이 존재한다.

두번쨰 원소를 포함하는 조합중에

[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 해당 원소로 시작"한다. 선택하고 다음원소를 반드시 뽑도록 지정하기 때문에 가능하다.