题目：
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[[1,2,2],[5]
]
这道题依然使用回溯法，与上一题有两点不通：
1. 数字不能重复使用，因而，下一次选择的数字，为当前索引的后一个 i + 1
2.给出的候选数字中有重复数字。
在不排序的情况下，比较 索引为 i 的数字与[begin , i ) 间的数字是否相同，若相同则处理下一个，这样会有重复的现象，排列不同，但数字相同，比如[1,7] [7,1] ；若比较 索引为 i 的数字与 [0,i)的数字是否相同，若相同则继续处理下一个，这样会有丢失的比如 [1,1,6] 。
因此对候选数字进行排序处理，当 i > begin , 如果 索引为 i 的数字，与 i - 1 相等，则继续处理下一个，既不会多，也不会少。
class Solution {
public:vector<vector<int> > res;void backtraceCombSum(vector<int> & cand, vector<int> &comb, int begin, int target){if(target <= 0){if(target == 0)res.push_back(comb);return;}for(int i = begin; i < cand.size(); i++){/* duplicate */ if(i > begin && cand[i] == cand[i-1]){continue;}comb.push_back(cand[i]);/* use once : begin = i + 1 */backtraceCombSum(cand,comb,i + 1,target - cand[i]);comb.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {res.clear();vector<int> combination;sort(candidates.begin(),candidates.end());backtraceCombSum(candidates,combination,0,target);return res;}
};
