Link to Question

MEDIUM

Combination Sum II

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

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

Example

Input:

candidates = [10,1,2,7,6,1,5], target = 8

Output:

[[1,1,6],[1,2,5],[1,7],[2,6]]

Explanation:
All unique combinations that sum to 8.

---

Constraints

• 1 ≤ candidates.length ≤ 100
• 1 ≤ candidates[i] ≤ 50
• 1 ≤ target ≤ 30

---

Solution: Backtracking

• Time Complexity: O(2^n)
• Space Complexity: O(n)

C++

class Solution {
    vector<vector<int>> ans;
    vector<int> temp;
public:
    void helper(vector<int>& c, int target, int index) {
        if (target == 0) {
            ans.push_back(temp);
            return;
        }
        if (target < 0 || index >= c.size()) return;
        for (int i = index; i < c.size(); i++) {
            if (i > index && c[i] == c[i-1]) continue;
            temp.push_back(c[i]);
            helper(c, target - c[i], i+1);
            temp.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& c, int target) {
        sort(c.begin(), c.end());
        helper(c, target, 0);
        return ans;
    }
};