39. Combination Sum

---

 

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

Combination Sum - LeetCode

 

고유한 정수 목록과 목표 값이 주어졌을 때, 요소들의 합으로 목표 값을 만족하는 부분 목록을 구하는 문제다.

풀어봤던 유형이지만 너무 오랜만에 풀어서 그런지 삽질을 좀 했다.

 

주요 고민 포인트로는

1. 요소를 중복으로 사용할 수 있기 때문에 매번 목록의 현재 위치부터 돌며 목표 값을 계산해야 했다.

2. [1,2,3]과 [3,2,1]은 동일한 결과로 치기 때문에 역으로 계산하면 안된다.

2가지 였다.

 

이런 포인트들을 위해 먼저 주어진 목록을 정렬하고 순차대로 돌며 계산한다.

---

class Solution
{
public:
    void solve(vector<int>& candidates, int index, int target, std::vector<std::vector<int>>& ret, vector<int>& sub_ret) {
        if (target == 0)
        {
            ret.push_back(sub_ret);
            return;
        }

        // point2. 역순 계산 방지를 위해 시작 지점을 특정 위치로 지정 후 증가만
        for (int i = index; i < candidates.size() && target >= candidates[i]; ++i)
        {
            sub_ret.push_back(candidates[i]);
            // point1. 요소의 중복 사용이 가능하기 때문에 i+1이 아닌 i로 전달
            solve(candidates, i, target - candidates[i], ret, sub_ret);
            sub_ret.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if (candidates.empty())
            return vector<vector<int>>();

        if (candidates.size() == 1 && candidates.at(0) == target)
            return vector<vector<int>> { candidates };

        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ret;
        vector<int> sub_ret;
        solve(candidates, 0, target, ret, sub_ret);
        return ret;
    }
};

---