题目链接：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 (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- 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]
这道题的要求是给定一组候选数字C和目标数字T，找到所有C中数字的组合，使其和为T。数字只可以选择1次。
备注：所有候选数字全为正数，要以非递减方式返回数字组合，结果不包含重复元素。
这道题和Combination Sum差不多，同样要求返回所有情况，同样是一个NP问题，同可以通过回溯方式，逐个找到所有情况。
不同之处是，这道题的候选数字里包含重复数字，而且每个数字只可以选择1次。因此，在递归处理的时候有些细节差别：
- 需要加入判重代码，即判断当前候选数字是否等于前一个。
- 递归的时候，应该从下一个候选数字开始，而不是当前的候选数字。
时间复杂度：O(???)
空间复杂度：O(nm)（结果数量）
1 class Solution
2 {
3 vector<vector<int> > vvi;
4 public:
5 vector<vector<int> > combinationSum2(vector<int> &num, int target)
6 {
7 sort(num.begin(), num.end());
8
9 vector<int> vi;
10 combinationSum2(num, target, 0, vi);
11 return vvi;
12 }
13
14 private:
15 void combinationSum2(vector<int> &num, int target, int i, vector<int> &vi)
16 {
17 if(target == 0)
18 {
19 vvi.push_back(vi);
20 return;
21 }
22
23 for(int j = i; j < num.size(); ++ j)
24 {
25 if(target < num[j])
26 break;
27
28 if(j > i && num[j] == num[j - 1])
29 continue;
30
31 vi.push_back(num[j]);
32 combinationSum2(num, target - num[j], j + 1, vi);
33 vi.pop_back();
34 }
35 }
36 };