39. Combination Sum

backtracking
如果问个数就是背包

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res, A = [], []
        candidates.sort()
        def dfs(b, s):
            if s == 0:
                res.append(A[:]) # 注意要copy!!!
                return
            for i in range(b, len(candidates)):
                x = candidates[i]
                if x > s:
                    break
                A.append(x)
                dfs(i, s - x)
                A.pop()
        dfs(0, target)
        return res

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def dfs(b, s, A):
            if s == 0:
                res.append(A)
                return
            for i in range(b, len(candidates)):
                x = candidates[i]
                if x > s:
                    break
                dfs(i, s - x, A + [x]) # 会触发copy
        dfs(0, target, [])
        return res

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(begin(candidates), end(candidates)); // 用来加速和去重
        dfs(candidates, 0, target);
        return res;
    }

    void dfs(const vector<int> &candidates, int b, int target) {
        if (target == 0) {
            res.push_back(v);
            return;
        }
        for (int i = b; i < candidates.size() && candidates[i] <= target; ++i) { // 注意candidates <= target
            v.push_back(candidates[i]); // 尝试寻找以candidates[i]开头的可行解
            dfs(candidates, i, target - candidates[i]);
            v.pop_back();
        }
    }

    vector<int> v;
    vector<vector<int>> res;
};