2017-03-20 09:35:38       个评论
我要投稿

代码

```//39. Combination Sum
vector> Solution::combinationSum(vector& candidates, int target)
{
vector> result;
if (candidates.empty())
return result;
sort(candidates.begin(), candidates.end());
result = combinationSumOrder(candidates, target);
return result;
}
vector> combinationSumOrder(vector& candidates, int target)
{
// candidates 是有序的
vector> result;
if(candidates.empty())
return result;
const int n = candidates.size();
for(auto it =candidates.begin(); it != candidates.end(); it++)
{
vector candidates_new(it,candidates.end());
int target_new=target - *it;
if(target_new == 0)
{
vector tmp;
result.push_back({*it});
break;
}
else if(target_new < 0)
{
break;
}
else
{
vector> result_tmp = combinationSumOrder(candidates_new,target_new);
if(result_tmp.empty())
continue;
for (int j = 0; j < result_tmp.size();j++)
{
result_tmp[j].insert(result_tmp[j].begin(),*it);
}

result.insert(result.end(),result_tmp.begin(),result_tmp.end());

}
}
return result;
}```