`
java-mans
  • 浏览: 11341093 次
文章分类
社区版块
存档分类
最新评论

从数列1,2,3.......n 中 随意取几个数,使其和等于 m

 
阅读更多

其实是个背包问题。

  1. voidFindSum(intsum,intn)//1到n和为m的所有组合
  2. {
  3. staticvector<int>l;
  4. if(n<=0||sum<=0)
  5. return;
  6. if(sum>n)
  7. {
  8. l.push_back(n);
  9. FindSum(sum-n,n-1);
  10. l.pop_back();
  11. FindSum(sum,n-1);
  12. }
  13. else
  14. {
  15. cout<<sum;
  16. for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
  17. cout<<""<<*iter;
  18. cout<<endl;
  19. //上面部分得到的是一种情况,但是还存在另一种情况,我们需要找出从1到sum-1里面是否存在值,它们的和等于sum
  20. if(sum!=1)
  21. FindSum(sum,sum-1);
  22. }
  23. }


扩展一:要求组合的个数一定

  1. voidFindSum1(intsum,intn,intnumber)//1到n中number个数和为m的所有组合
  2. {
  3. staticvector<int>l;
  4. if(sum<=0||n<=0||number<=0||n<number)
  5. return;
  6. if(sum>n)
  7. {
  8. l.push_back(n);
  9. FindSum1(sum-n,n-1,number-1);
  10. l.pop_back();
  11. FindSum1(sum,n-1,number);
  12. }
  13. elseif(number==1)
  14. {
  15. cout<<sum;
  16. for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
  17. cout<<""<<*iter;
  18. cout<<endl;
  19. }
  20. else
  21. {
  22. if(sum!=1)
  23. FindSum1(sum,sum-1,number);
  24. }
  25. }


扩展二:给定不重复数组a, 求数组a中number个数和为sum的所有组合,其中n为(数组长度-1)

  1. voidFindSum2(int*a,intsum,intn,intnumber)//给定不重复数组a,求数组a中number个数和为sum的所有组合,其中n为(数组长度-1)
  2. {
  3. staticvector<int>l;
  4. if(number==0&&sum==0)
  5. {
  6. for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
  7. cout<<*iter<<"";
  8. cout<<endl;
  9. return;
  10. }
  11. if(sum<0||n<0||n<number-1)
  12. return;
  13. l.push_back(a[n]);
  14. FindSum2(a,sum-a[n],n-1,number-1);
  15. l.pop_back();
  16. FindSum2(a,sum,n-1,number);
  17. }

扩展三:不重复数组中和等于sum的所有组合,n是(数组的长度-1)

  1. voidFindSum3(int*a,intsum,intn)//不重复数组中和等于sum的所有组合,n是(数组的长度-1)
  2. {
  3. staticvector<int>l;
  4. if(sum==0)
  5. {
  6. for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
  7. cout<<*iter<<"";
  8. cout<<endl;
  9. return;
  10. }
  11. if(sum<0||n<0)
  12. return;
  13. l.push_back(a[n]);
  14. FindSum3(a,sum-a[n],n-1);
  15. l.pop_back();
  16. FindSum3(a,sum,n-1);
  17. }


扩展四:给定可重复数组a(首先要将数组a排序,递增递减都可以), 求数组a中number个数和为sum的所有组合,其中n为(数组长度-1)

  1. voidFindSum4(int*a,intsum,intn,intnumber)//给定可重复数组a(首先要将数组a排序,递增递减都可以),求数组a中number个数和为sum的所有组合,其中n为(数组长度-1)
  2. {
  3. staticvector<int>l;
  4. if(number==0&&sum==0)
  5. {
  6. for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
  7. cout<<*iter<<"";
  8. cout<<endl;
  9. return;
  10. }
  11. if(sum<0||n<0||n<number-1)
  12. return;
  13. l.push_back(a[n]);
  14. FindSum4(a,sum-a[n],n-1,number-1);
  15. l.pop_back();
  16. if(a[n]==a[n-1])
  17. return;
  18. FindSum4(a,sum,n-1,number);
  19. }


扩展五:可重复数组(首先要将数组a排序,递增递减都可以)中和等于sum的所有组合,n是(数组的长度-1)

  1. voidFindSum5(int*a,intsum,intn)//可重复数组(首先要将数组a排序,递增递减都可以)中和等于sum的所有组合,n是(数组的长度-1)
  2. {
  3. staticvector<int>l;
  4. if(sum==0)
  5. {
  6. for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
  7. cout<<*iter<<"";
  8. cout<<endl;
  9. return;
  10. }
  11. if(sum<0||n<0)
  12. return;
  13. l.push_back(a[n]);
  14. FindSum5(a,sum-a[n],n-1);
  15. l.pop_back();
  16. if(a[n]==a[n-1])
  17. return;
  18. FindSum5(a,sum,n-1);
  19. }
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics