[BackTrack][Medium] 39. Combination Sum

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

 

정수 배열과 target 값이 주어 질 때, 정수 값의 합이 target이 되는 값들을 찾아라.

 

 

이전 문제보다는 종료 조건이 명확하므로, 조금 더 쉽다. 

 

* 종료 조건 

* loop의 재시작 index 지점

* 다음 back track으로 넘기는 index

 

위 로직에 유의하면서 코드를 만든다. 

 

코드

 void combiBT(int sum, vector<vector<int>>& vRet, vector<int>& vCur, vector<int>& candidates, int idx)
{
    if(sum <= 0)
    {
        if(sum == 0)
            vRet.push_back(vCur);                // 합이 target이 될때 값을 모은다.
        return;
    }

    for(int q = idx; q < candidates.size(); ++q) // 전달 받은 지점 inde에서 재시작
    {
        vCur.push_back(candidates[q]);           // 지금 시작 시점에서 재 시작토록 backtrack 호출
        combiBT(sum-candidates[q], vRet, vCur, candidates, q);
        vCur.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
{
    vector<vector<int>> vRet;
    vector<int> vCur;
    combiBT(target, vRet, vCur, candidates, 0);
    return vRet;
}

 

 

결과