[Leetcode,c++] Combination Sum II

문제

Combination Sum II - LeetCode

 

코드

class Solution {
public:
    void dfs(int index, vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>&current){

        if(target==0){
            ans.push_back(current);
            return;
        }
        for(int i=index; i<candidates.size(); i++){
            if(i>index && candidates[i]==candidates[i-1]) continue;
            if(candidates[i]>target) break;
            current.push_back(candidates[i]);
            dfs(i+1,candidates,target-candidates[i],ans,current);
            current.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int>current;
        vector<vector<int>>ans;
        dfs(0, candidates, target, ans, current);
        return ans;
    }

};

 

풀이

이전 Combination Sum I 문제와 입력에 중복된 값이 들어온다는 것 빼고는 동일한 문제입니다.

candidates = {1,1,2,3} , target = 3일 때 중복처리를 해주지 않으면 [1,2] , [1,2] 값이 두 쌍이 생기기 때문에 

if(i>index && candidates[i]==candidates[i-1]) continue;

위와 같은 조건을 추가해주어 중복을 처리해주었습니다.

만약 위 조건문으로 처리해주지 않고 아래와 같이 짠다면 시간 초과가 뜹니다.

class Solution {
public:
    map<vector<int>,int>visited;
    
    void dfs(int index, vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>&current){
        
        if(target==0){
            if(visited[current]==0){
            ans.push_back(current);
                visited[current]=1;
            }
            return;
        }
        for(int i=index; i<candidates.size(); i++){
            // if(i>index && candidates[i]==candidates[i-1]) continue;
            if(candidates[i]>target) break;
            current.push_back(candidates[i]);
            dfs(i+1,candidates,target-candidates[i],ans,current);
            current.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int>current;
        vector<vector<int>>ans;
        dfs(0, candidates, target, ans, current);
        return ans;
    }
    
};