[LeetCode / C++]

문제 바로가기: https://leetcode.com/problems/combination-sum/description/

class Solution {
    vector<int> arr;
    vector<vector<int>> combinations;
    
    void func(vector<int>& candidates, int target, int k, int idx){
        int sum = 0;
        for(int i = 0; i < arr.size(); i++) sum += arr[i];

        if(sum > target) return; // 큰 경우는 가지치기
        if(sum == target){
            combinations.push_back(arr);
            return;
        }
        
		// unique combination: idx 넘기기
        // unlimited candidates: i 그대로 넘기기
        for(int i = idx; i < candidates.size(); i++){
            arr.push_back(candidates[i]);
            func(candidates, target, k + 1, i); 
            arr.pop_back();
        }
    }

    public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        func(candidates, target, 0, 0);
        return combinations;
    }
};