# [40\. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/)

:::spoiler Solution

class Solution {
private:
    vector<vector<int>> res;
    vector<int> comb;    
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0);
        return res;
    }
    void backtracking(vector<int>& candidates, int target, int start)
    {
        if (target == 0) res.push_back(comb);
        if (target < 0) return;

        unordered_set<int> seen;

        for (int i = start; i < candidates.size(); i++)
        {
            if (seen.count(candidates[i])) continue;
            comb.push_back(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            comb.pop_back();
            seen.insert(candidates[i]);
        }
    }    
};

- T: $O(2^N)$
- S: $O(N)$
:::