首页 > 代码库 > 【leetcode】Combination Sum

【leetcode】Combination Sum

2024-08-10 14:35:37   219人阅读

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

利用递归搜索，同时剪枝就可以
 
 1 class Solution { 2  3 public: 4  5     vector<vector<int> > combinationSum(vector<int> &candidates, int target) { 6  7          8  9         sort(candidates.begin(),candidates.end());10 11         vector<vector<int> > result;12 13         vector<int> tmp;14 15  16 17         backtracking(result,candidates,target,tmp,0,0);18 19         20 21         return result;22 23     }24 25     26 27     void backtracking(vector<vector<int> > &result,vector<int> &candidates, int &target,vector<int> tmp, int sum,int index)28 29     {30 31  32 33         if(sum==target)34 35         {36 37             result.push_back(tmp);38 39             return;40 41         }42 43         else44 45         {46 47             int sum0=sum;48 49             //注意index50 51             for(int i=index;i<candidates.size();i++)52 53             {54 55                 tmp.push_back(candidates[i]);56 57                 sum=sum0+candidates[i];58 59                 if(sum>target)60 61                 {62 63                     break;64 65                 }66 67                 backtracking(result,candidates,target,tmp,sum,i);68 69                 tmp.pop_back();70 71             }            72 73         }        74 75     }76 77 };

 

【leetcode】Combination Sum


联系
我们