[BackTrack][Medium] 40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/description/

 

주어진 정수 배열의 합이 target이 되는 조합을 찾아라. 

이때 정수에는 중복값이 있을 수 있다. 

결과에서 중복 결과를 제거하라. 

 

Subset II와 거의 같은 풀이의 문제. 

같은 로직으로 중복을 제거 할 수 있다. 

 

코드 

void combinationSum2BT(int idx, vector<vector<int>>& vRet, vector<int>& vCur, vector<int>& candidates, int target)
{
    if(target <= 0)
    {
        if(target == 0)
            vRet.push_back(vCur);
        return;
    }

    for(int q = idx; q < candidates.size(); ++q)
    {
        if(q>idx && candidates[q-1]==candidates[q])
            continue;

        vCur.push_back(candidates[q]);
        combinationSum2BT(q+1, vRet, vCur, candidates, target-candidates[q]);
        vCur.pop_back();
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
{
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> vRet;
    vector<int> vCur;

    combinationSum2BT(0, vRet, vCur, candidates, target );
    return vRet;
}

 

 

결과