LeetCode : 39. Combination Sum

backtracking문제를 너무 오랜만에 풀어서 약간 푸는 데 생각보다? 오래걸렸다.

 

[문제 설명]

Input: candidates = [2,3,6,7], target = 7

다음과 같이 배열이 주어지면 그 안에서 합이 target이 될 수 있는 조합을 찾는 문제이다.

위와 같은 input이라면,

Output: [[2,2,3],[7]] 이러한 결과가 나올 수 있다.

주의할 점은!! [2, 2, 3] = [2, 3, 2] = [3, 2, 2] 모두 같은 값으로 취급한다는 것!

 

[메인 로직]

dfs함수의 인자값으로 지금까지의 값의 합 / 지금까지의 값들을 넣는 벡터 / candidates벡터 / target값 / 다음에 탐색을 시작할 idx값을 넣어주었다.

만약, 다음에 탐색을 시작할 idx값을 넣어주지 않으면 0번째 idx부터 다시 탐색을 시작하기 때문에,,,

[2, 2, 3], [3, 2, 2]와 같은 중복 결과들이 나올 수 밖에 없다!!

 

class Solution {
public:
    vector<vector<int>> ans;
    
    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++){
            v.push_back(candidates[i]);
            dfs(sum+candidates[i], v, candidates, target, i);
            v.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        for(int i=0; i<candidates.size(); i++){
            vector<int> temp;
            temp.push_back(candidates[i]);
            dfs(candidates[i], temp, candidates, target, i);
        }
        
        return ans;
    }
};