注意和39题区别,当前层值相同则跳过
回溯法
void cb2help(vector<vector<int>> &res,vector<int> &v,int target,unsigned int i,vector<int> recp)
{
if(target<0) return;
else if(target==0)
{
res.push_back(recp);
return;
}
for(unsigned int k=i;k<v.size();++k)
{
if(k>i&&v[k]==v[k-1]) continue;
recp.push_back(v[k]);
cb2help(res,v,target-v[k],k+1,recp);
recp.pop_back();
if(target-v[k]<0) return;
}
}
vector<vector<int>> combinationSum2(vector<int>& v, int target)
{
sort(v.begin(),v.end());
vector<vector<int>> res;
vector<int> recp;
cb2help(res,v,target,0,recp);
return res;
}