[Leetcode,c++] Combination Sum

문제

Combination Sum - LeetCode

 

 

코드

class Solution {
    map<vector<int>,int>duplicate;

public:
    vector<vector<int>>ans;
    void dfs(vector<int> &candidates,int &target,int sum,vector<int> route){
        if(sum==target){
            sort(route.begin(),route.end());
            if(duplicate[route]==0){
                duplicate[route]++;
                ans.push_back(route);
                return;
            }
        }
        else if(sum>target) return;
        else{
            for(int i=0; i<candidates.size(); i++){
                vector<int>temp(route);
                temp.push_back(candidates[i]);
                dfs(candidates,target,sum+candidates[i],temp);
            }
        }
        return;
    }

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

 

풀이

백트래킹을 활용하여 dfs로 계속 candidates 배열을 깊이 탐색하여 숫자를 더해가면서 target숫자가 된다면 return 하는 방식으로 구현했습니다.

유의할 점은  {1,1,3}, {1,3,1}의 경우 같은 경우이기 때문에 하나로 정렬을 한 상태인 {1,1,3} 하나로 보아야합니다. 따라서 저는 해쉬 테이블 map을 활용하여 방문 처리를 하여 동일한 경우를 제거해주었습니다.

 

회고

위의 풀이는 시간과 메모리가 압도적으로 좋지않았습니다. 그래서 일주일 뒤에 다시 생각하여 풀어보았습니다.

아래는 다시 생각하여 풀이한 코드입니다.

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

for문을 0이 아니라 index 부터 돈다면 뒤로 넘어가는 일이 없어서 {1,1,3}, {1,3,1}와 같은 경우가 생기지 않습니다. 또한 for문에서 그 값이 유효한 값인지 미리 검사를 하여 탐색을 하는경우의 수를 줄였습니다.