[LeetCode] C++. 39. Combination Sum

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

 

문제

 

문제 분석

- DFS를 이용해서 합이 target과 같을 때만 결과로 넣으면서 반복하고, target 값을 넘어가면 그 즉시 종료하도록 하면 됩니다. 조합이기 때문에 각 요소의 순서가 바뀐 것은 하나로 보아야 하기 때문에 정렬 후에 자기 자신 이상의 값들만 다음 번 요소로 사용할 수 있도록 해야합니다.

- 반대로 sum을 계산하면서 합이 아니라 값을 target에서 감소시키는 방향으로도 풀 수 있을 것입니다.

 

풀이

class Solution {
private:
    vector<vector<int>> result;
    void dfs(vector<int>& candidates, vector<int>& current, int target, int start){
        int sum = accumulate(current.begin(), current.end(), 0);

        if(sum == target){
            result.push_back(current);
        }

        for(int i = start; i < candidates.size(); ++i){
            if(sum + candidates[i] > target){
                return;
            }
            current.push_back(candidates[i]);
            dfs(candidates, current, target, i);
            current.pop_back();

        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> current;
        dfs(candidates, current, target, 0);

        return result;
    }
};