[Backtracking][Medium] 216. Combination Sum III

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

Combination Sum III - LeetCode

 

Q. 1 ~ 9개의 숫자를 k 번 사용하여 그 합을 n 을 만든다고 할때, 만들 수 있는 모든 조합을 찾아라.

 

 

 

 

Solution

 Backtracking의 몇개의 기본 문제 중의 하나. 

 backtrack 포맷에 익숙하다면 어렵지 않게 풀릴 것이다. 

 

void combi_help(vector<vector<int>>& vRet, vector<int>& vCur, int targetSize, int targetSum, int start)
{
    if (vCur.size() == targetSize)
    {
        int sum = 0;
        for (int q = 0; q < vCur.size(); ++q)
            sum += vCur[q];
        if (sum == targetSum)
            vRet.push_back(vCur);
        return;
    }

    // 더하는 수를 중복해서 사용하면 안되므로, k의 시작은 달라져야 한다.
    for (int k = start; k <= 9; ++k)
    {
        vCur.push_back(k);
        combi_help(vRet, vCur, targetSize, targetSum, k + 1);
        vCur.pop_back();
    }
}

vector<vector<int>> combinationSum3(int k, int n)
{
    vector<vector<int>> vRet;
    vector<int> vCur;
    combi_help(vRet, vCur, k, n, 1);
    return vRet;
}

 

 

음.