Combination Sum

[fkdl0048]

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> currentCombiation;
        backTrack(candidates, 0, target, currentCombiation, result);
        return result;
    }

private:
    void backTrack(vector<int>& candidates, int startIdx, int target, vector<int>& currentCombiation, vector<vector<int>>& result){
        if (target == 0) {
            result.push_back(currentCombiation);
            return;
        }

        if (target < 0) {
            return;
        }

        for (int i = startIdx; i < candidates.size(); i++) {
            currentCombiation.push_back(candidates[i]);
            backTrack(candidates, i, target - candidates[i], currentCombiation, result);
            currentCombiation.pop_back();
        }
    }
};

• 백트래킹 개념이 정말 잘 설명되는 문제, 중복이 가능하기에 i ++을 하지 않는다.