Backtracking

40. Combination Sum II

Jimmy (xiaoke) Shen

·

Follow

Dec 25, 2020

--

Listen

Share

class Solution {
public:
    void dfs(set<vector<int>>& ret, vector<int>& candidates, int i, int target, vector<int>& curr) {
        if (target == 0) {
            ret.insert(curr);
            return;
        }
        if (target < 0 || i >= candidates.size()) return;
        dfs(ret, candidates, i + 1, target, curr);
        curr.push_back(candidates[i]);
        dfs(ret, candidates, i + 1, target - candidates[i], curr);
        curr.pop_back();
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        set<vector<int>> ret;
        sort(candidates.begin(), candidates.end());
        const int n = candidates.size();
        vector<int> curr;
        dfs(ret, candidates, 0, target, curr);
        vector<vector<int>> finRet(ret.begin(), ret.end());
        return finRet;
    }
};