39. Combination Sum

解題思路

也是經典的題型。

如果要確保 combination 是唯一的，用 start 標記起始點可以避免重複拿取 element，以至於產生相同的組合。

程式碼

class Solution {
public:
    void helper(vector<int>& candidates, vector<vector<int>>& ans, vector<int> result, int target, int start)
    {
        if(target == 0)
            ans.push_back(result);
        if(target < 0)
            return ;

        for(int i=start; i<candidates.size(); i++)
        {
            vector<int> result_new = result;
            result_new.push_back(candidates[i]);
            helper(candidates, ans, result_new, target - candidates[i], i);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> result;
        helper(candidates, ans, result, target, 0);
        return ans;
    }
};