[Backtracking][Medium] 39. Combination Sum

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 정수 배열인 candidates 와 target 이 주어질 때, 그 합이 target이 되는 유일한 candidates 조합들을 모두 찾아라.

 

 

Solution. 

 Backtrack의 기본은 모든 원소를 순회하면서 하나씩 넣어 리스트를 만들고, 그 결과를 조건에 맞나 확인하는 것이 기본 구조이다. 

 여기서, 결과를 확인하는 방법, 

 리스트에 하나씩 넣을때의 조건들 

 등 만이 문제별로 상이할 따름이다. 

 

 이 문제의 최종 조건은 리스트의 원소 합이 target인지 확인하는 것이다. 

 또한 리스트에 삽입 조건은, 이전에 넣은 것의 위치에서 시작하는 것이다. 

 

 따라서 해당 로직을 기초로 코드를 작성해 본다. 

 

 void combinationSum_BT(vector<vector<int>>& vRet, vector<int>& candidates, int target, vector<int>& cur, int idxStart)
{
    // 탈출 조건 - 그 합이 target이 되는가.
    int sum = 0;
    for (int q = 0; q < cur.size(); ++q)
    {
        sum += cur[q];
    }
    if (sum >= target)
    {
        if (sum == target)
            vRet.push_back(cur);
        return;
    }

    // 삽입 조건 - 이전 index (idxStart)로부터 insert를 시작한다.    
    for (int k = idxStart; k < candidates.size(); ++k)
    {
        cur.push_back(candidates[k]);
        combinationSum_BT(vRet, candidates, target, cur, k);
        cur.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
{
    vector<vector<int>> vRet;
    vector<int> cur;
    combinationSum_BT(vRet, candidates, target, cur, 0);
    return vRet;
}

 

 

합당한 결과를 얻었다.