题意：
在集合candidates中选出任意多个元素，使得他们的和为target，返回所有的组合，以升序排列。
思路：
难点在于如何去重，比如集合{1，1，2}，target=3，那么只有一个组合就是1+2=3，而不是两个。
DFS解决，每次考虑candidates[i]取还是不取，但是这样子还是会产生重复，这里只需要一个技巧就可以使得没有重复出现。如果当前元素已经被考虑过取了，那么在考虑不取的时候，i后面的与candidates[i]相同的都要跳过。观察一下可以发现，如果有一串相同的数字出现的话，只会考虑取到前面的那几个元素而已。
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
n=target;
sort(candidates.begin(),candidates.end());
DFS(,,candidates,tmp);
return ans;
}
void DFS(int pos,int sum,const vector<int>& old,vector<int>& num)
{
if(sum==n)
{
ans.push_back(num);
return ;
}
if(sum>=n||pos>=old.size()) return;
for(;pos<old.size(); pos++)
{
num.push_back(old[pos]);
DFS(pos+,sum+old[pos],old,num);
num.pop_back();
while(pos<old.size()&&old[pos]==old[pos+]) pos++;
}
}
private:
vector<vector<int>> ans;
vector<int> tmp;
int n;
};
AC代码