040.md

40. Combination Sum II

Solution 1

// DFS
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> cur;
        _combinationSum2(candidates, target, 0, cur, ans);
        return ans;
    }

    void _combinationSum2(vector<int>& candidates, int target, int idx,
                          vector<int>& cur, vector<vector<int>>& ans) {
        if (target == 0) {
            ans.push_back(cur);
            return;
        }
        int i = idx;
        while (i < candidates.size()) {
            if (candidates[i] > target)
                break;
            cur.push_back(candidates[i]);
            _combinationSum2(candidates, target - candidates[i], i + 1, cur, ans);
            cur.pop_back();
            while (i + 1 < candidates.size() && candidates[i] == candidates[i + 1])
                i++;
            i++;
        }
        return;
    }
};