Problem Statement:

Given a collection of candidate numbers (candidates) 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.

Note: The solution set must not contain duplicate combinations.

Example 1:

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

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Solution:

The approach is to run DFS starting with zeroth index. At every index, we either

include it and run DFS again with reduced target and next index (since repetition is not allowed), OR
skip current and next indices till we get a different value and then start DFS with the first index which has a different value and with the same target.

 
class Solution {
public:
    void dfs(int t, int idx, vector<vector<int>>&res, vector<int>&r, vector<int>&nums)
    {
        if (t==0){res.push_back(r); return;}
        if (t<0 || idx==nums.size()) return;
        r.push_back(nums[idx]);
        dfs(t-nums[idx], idx+1, res, r, nums);
        r.pop_back();
        idx++;
        while(idx<nums.size() && nums[idx]==nums[idx-1]) idx++;
        dfs(t, idx, res, r, nums);
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        sort(candidates.begin(),candidates.end());
        for(int k: candidates) cout<<k<<','; cout<<endl;
        vector<vector<int>>res;
        vector<int>r;
        dfs(target, 0, res, r, candidates);
        return res;
        return vector<vector<int>>(res.begin(),res.end());
    }
};

$TC: O(2^n), SC: O(2^n)$