Given a collection of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.
Each number inCmay only be usedoncein the combination.
Note:
All numbers (including target) will be positive integers.Elements in a combination (, … ,≤a2≤ … ≤ak).The solution set must not contain duplicate combinations.
For example, given candidate set10,1,2,7,6,1,5and target8,A solution set is:[1, 7][1, 2, 5][2, 6][1, 1, 6]
主要是需要注意如果C中包含了相同的元素的处理方法
如果两个数字相同，前一个数字没有用，那么后面相同的数字也不应该使用，如果前面的数字使用了，，可以考虑后面的数字的使用
class Solution {public:vector<vector<int> > combinationSum2(vector<int> &num, int target) { //<DFS算法vector<vector<int> > result;vector<int> combination;sort(num.begin(), num.end());result.clear();internalCombinationSum2(num, 0, 0, target, combination, result);return result;}//<这里有一个问题就是如果C中有重复的数据，如果前一个数据能够放入，后面相同的就可以放入//<如果前面的数据不能放入，那么后面也就不用放入，注意是按照升序排列的void internalCombinationSum2(vector<int> &num,int start,int sum,int target,vector<int> &combination,vector<vector<int> > &result) {int size = num.size();if (sum == target) {result.push_back(combination);return;}else if ((start >= size) || (sum > target)) {return;}for (int i = start; i < size; ) {combination.push_back(num[i]);internalCombinationSum2(num, i + 1, sum + num[i], target, combination, result);combination.pop_back();i++;while (i < size) {if (num[i] == num[i-1]) {++i;}else {break;}}}}};
夺冠那一刻,豪情万丈!登顶那一瞬,万众瞩目!那一刻的嫣然一笑,
