Leetcode 40: Combination sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

这个题目和combination sum不同的地方在于，有重复的元素，每个元素最多只能用一次，说明一个元素可以用0次或者1次，DFS每一层有两分支，其实这个题目本质和all subsets of a string with duplicate 是完全相同的， 对给定的nums求出所有的subsets，同时判断这些subsets的和是否与target相同。
all subsets of a string with duplicate去重的做法是，在跳过一个元素之前，跳过所有duplicate的元素。
time complexity: O(2^n) space complexity: O(n)
class Solution {
private:
    void DFS(vector<vector<int>> &rst, vector<int> solu, vector<int>& candidates, int target, int cur) {
        if (target == 0) {
            rst.push_back(solu);
            return;
        }
        if (cur == candidates.size() || target < 0) return;
        //use this element
        solu.push_back(candidates[cur]);
        DFS(rst, solu, candidates, target - candidates[cur], cur+1);
        solu.pop_back();
        //don't use this element
        //deduplicate the duplicate elements in solving the subsets.
        while (cur < candidates.size()-1 && candidates[cur] == candidates[cur+1]) cur++;
        DFS(rst, solu, candidates, target, cur+1);
    }
public:
//DFS: ALL SUBSET OF elements + sum = target return;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> rst;
        vector<int> solu;
        sort(candidates.begin(), candidates.end());
        //sanity check
        if (candidates.size() == 0) return rst;
        DFS(rst, solu, candidates, target, 0);
        return rst;
    }
};