LeedCode : 40. Combination Sum II

앞서 풀었던 Combination Sum 과 매우 유사한 문제이다.

하지만, 이 문제는 중복허용이 되지 않는 다는 것!

 

[메인 로직]

ex) 10, 1, 2, 7, 6, 1, 5 / target = 8이라면

먼저 오름차순 정렬해준다.

1, 1, 2, 5, 6, 7, 10 으로 정렬된 상태에서 idx = 0부터 target = 8인 조합을 찾아나가면

[1, 2, 5]를 완성할 수 있다.

하지만 idx = 1도 '1'이기 때문에 중복된 결과를 만들게 된다.

따라서, 중복된 값을 만들지 않기 위해!!

for문 탐색할 때, if(i>start && candidates[i]==candidates[i-1])이라면 continue를 해서 중복을 막았다.

 

class Solution {
public:
    vector<vector<int>> ans;
    map<int, int> m;
    
    void dfs(int sum, vector<int>& v, vector<int>& candidates, int target, int start){
        if(sum>target){
            return;
        }
        if(sum==target){
            ans.push_back(v);
            return;
        }
        for(int i=start; i<candidates.size(); i++){
            if(i>start && candidates[i]==candidates[i-1]) continue;
            v.push_back(candidates[i]);
            dfs(sum+candidates[i], v, candidates, target, i+1);
            v.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for(int i=0; i<candidates.size(); i++){
            if(m.count(candidates[i])!=0) continue;
            m[candidates[i]] = 1;
            vector<int> temp;
            temp.push_back(candidates[i]);
            dfs(candidates[i], temp, candidates, target, i+1);
        }
        
        return ans;
    }
};