40. Combination Sum II

backtracking
对比39. Combination Sum这道题candidates可能有dup且每个candidate只能用一次

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res, A = [], []
        candidates.sort()
        def dfs(b, s):
            if s == 0:
                res.append(A[:])
                return
            for i in range(b, len(candidates)):
                x = candidates[i]
                if x > s:
                    break
                if i > b and x == candidates[i - 1]:
                    continue
                A.append(x)
                dfs(i + 1, s - x)
                A.pop()
        dfs(0, target)
        return res

class Solution:
    def combinationSum2(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
                if i > b and x == candidates[i - 1]:
                    continue
                dfs(i + 1, s - x, A + [x])
        dfs(0, target, [])
        return res

class Solution {
public:
    vector<vector<int>> combinationSum2(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) {
            if (i > b && candidates[i] == candidates[i - 1]) continue; // 去重
            v.push_back(candidates[i]);
            dfs(candidates, i + 1, target - candidates[i]); // 从下一个开始
            v.pop_back();
        }
    }

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