[LeetCode] 39. Combination Sum

這題四年前有寫過，最近在做複習

我用的方式應該算是很general的方式來解

backtracking or DFS(?) 不過缺點會用掉一個nlogn的sorting

然後從小的開始選擇要不要pick到vector cur中，然後依序遞迴下去

一開始只有單純遞迴，發現會算到重覆的case

只好改用loop避開

push就是選了這個subset，因為可以重複使用，這裡index不++，進入遞迴

pop的狀況就是不選or不再選這個subset

看討論區基本上要不要pick的題目(subset 排列組合之類的)好像都可以這樣的方式解

class Solution {
public:
    vector<vector<int>> res;
    vector<int> candidates;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        
        sort(candidates.begin(), candidates.end());
        this->candidates = candidates;
        vector<int> dummy;
        
        helper(0, target, dummy);
        return res;
    }
    
    void helper (int i, int target, vector<int>& cur) {
        if (target == 0) {
            res.emplace_back(cur); 
            return;
        }

        
        for (; i < candidates.size(); i++) {
            if(candidates[i] > target)
                break;
            
            cur.emplace_back(candidates[i]);
            helper(i, target-candidates[i], cur);
            cur.pop_back();
        }
    

    }
};