首页 > 代码库 > [LeetCode] Combination Sum
[LeetCode] Combination Sum
1 void func(const vector<int> & candidates, int target, vector<int> & path,
int cur , int sum , vector<vector<int> > & ret ) 2 { 3 if( sum == target ) { 4 ret.push_back(path); 5 // path.pop_back(); // 6 return; 7 } 8 else if( cur >= candidates.size() ) { 9 // if(!path.empty()) path.pop_back();10 return;11 }12 13 for(int i = 0; sum + i * candidates[cur] <= target ; i++)14 {15 for(int j = 0 ;j < i;j++)16 path.push_back(candidates[cur]);17 18 func( candidates, target, path, cur+1, sum + i*candidates[cur] , ret);19 20 for(int j = 0 ; j< i;j++)21 path.pop_back();22 } 23 24 }25 vector<vector<int> > combinationSum(vector<int> &candidates, int target) {26 27 vector<vector<int> > ret ;28 vector<int> path;29 sort(candidates.begin() , candidates.end());30 func( candidates, target, path, 0, 0 , ret);31 return ret;32 }
全部背包问题。由于要生成并保存所有可行解，必须使用DFS递归。
代码技巧：函数参数使用引用。（如何保证互不影响？？）
扩展问题：如果要求可行解的个数呢？下面给出递归和递推两种方法。
代码技巧：递归的难点在递归的层级和边界，这两个递归的边界处理，各有技巧。
1 int count(const vector<int> & vec , int cur , int target){ 2 3 if( A[cur][target] >=0 ) return A[cur][target]; 4 5 if( target == 0 ) return A[cur][target] = 0; 6 7 if( cur == vec.size()-1 ) { 8 return A[cur][target] = ( target % vec[cur] ? 0 : 1 ); 9 }10 11 int i , sum = 0;12 for( i=0; i < target ; i+= vec[cur])13 sum += count(vec,cur+1,target-i);14 if(i==target) sum++;15 return A[cur][target]=sum;16 }
1 int count(const vector<int> & vec ,int key) 2 { 3 int i,j,k; 4 for(i = 1 ; i < M ; i++) { 5 B[i][0] = 1 ; 6 } 7 for(j=1; j<=N; j++){ 8 B[M-1][j] = ( j % vec[M-1] ? 0 : 1); 9 }10 11 for ( i = M-2 ; i >= 0 ; i--)12 for( j = 1; j<= key ;j++)13 {14 for( k = 0; k <= j; k += vec[i])15 B[i][j] += B[i+1][j-k];16 }17 18 return B[0][key];19 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。