Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        std::sort(candidates.begin(), candidates.end());
        vector<int> curr;
        dfs(candidates, target, 0, ans, curr);
        return ans;
    }
private:
    void dfs(const vector<int>& candidates, 
             int target, int s, 
             vector<vector<int>>& ans,              
             vector<int>& curr) {
        if (target == 0) {
            ans.push_back(curr);
            return;
        }
        
        for (int i = s; i < candidates.size(); ++i) {
            int num = candidates[i];
            if (num > target) return;
            if (i > s && candidates[i] == candidates[i - 1]) continue;
            curr.push_back(num);
            dfs(candidates, target - num, i + 1, ans, curr);
            curr.pop_back();
        }
    }
};

    /*
class Solution {
public:

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> sol;
        vector<int> ans;
        if (candidates.size() == 0) {
            return sol;
        }
        helper(candidates, 0, ans, sol, target);
        return sol;
    }
    
    void helper(vector<int>& candidates, int idx, vector<int> ans,
                vector<vector<int>>& sol, int target) {
        if (idx == candidates.size() || target == 0) {
            if (target == 0) {
                sol.push_back(ans);
            }
            return;
        }
        
        for (int i = idx; i < candidates.size(); i++) {
            if (target - candidates[i] >= 0) {
                ans.push_back(candidates[i]);
                helper(candidates, i + 1, ans, sol, target - candidates[i]);
                ans.pop_back();
            }
            helper(candidates, i + 1, ans, sol, target);
        }
    }
};
*/