[LeetCode] 40. Combination Sum II

문제 URL : https://leetcode.com/problems/combination-sum-ii/

Combination Sum II - LeetCode

 

문제 접근법 : 

candidates안에있는 수를 뽑아서 전부 더했을때 target 되는 경우의 수를 구하는 문제입니다.

물론 중복은 제거해야합니다.

 

target이 30이고 candidate가 50까지입니다. 그얘긴 target보다 큰수는 볼필요가 없습니다.

카운팅정렬하여 백트래킹을이용해서 모든경우의수를 구하면 빠르게 구할수있습니다.

 

소스코드 : 

class Solution {
public:
vector<int>num,v;
vector<vector<int>> res;
void dfs(vector<int>& can,int target,int idx=1){
    if(target==0){
        res.push_back(v);
        return;
    }

    for(int i=idx;i<=target;i++){
        if(num[i]>0&&target-i>=0){
            v.push_back(i);
            num[i]--;
            dfs(can,target-i,i);
            num[i]++;
            v.pop_back();
        }
    }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    num=vector<int>(51);
    for(int t:candidates)num[t]++;
    dfs(candidates,target);
    for(int i=0;i<res.size();i++){
        for(int j:res[i]){
            cout<<j<<" ";
        }
        cout<<endl;
    }
    return res;
}
};

 

 

 

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.