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.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] ]Subscribe to see which companies asked this question
中间过程用set保证唯一性，结果进行一次转换。
static int m[100]; class Solution { public: void backtrack(vector<int>& can,const int target,vector<int> temp,int t,int tempSum,set<vector<int>>& s1) { if(tempSum==target) { sort(temp.begin(),temp.end()); if(s1.find(temp)==s1.end()) { s1.insert(temp); } return ; } else { for(int i=t+1;i<can.size();++i) { if(m[i]==0&&(tempSum+can[i])<=target) { m[i]=1; temp.push_back(can[i]); backtrack(can,target,temp,i,tempSum+can[i],s1); temp.pop_back(); m[i]=0; } } return ; } } vector<vector<int>> combinationSum2(vector<int>& can, int target) { vector<int> temp; set<vector<int>> s1; for(int i=0;i<can.size();++i) { if(can[i]<=target) { m[i]=1; temp.push_back(can[i]); backtrack(can,target,temp,i,can[i],s1); temp.pop_back(); m[i]=0; } } return vector<vector<int>>(s1.begin(),s1.end()); } };