首页 > 代码库 > 两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数, 使其和为 m

两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数, 使其和为 m

/*

输入两个数m和n ,从数列1,2,3,4,.....n这些数中挑选几个

使得和为m,找出所有的这样的组合

*/

void FindSum(int m,intn,vector<int>& vec)

{

    if(m < 0 || n < 0)

     return ;

    if(m == 0)

    {

         vector<int>::iterator itr = vec.begin();

         

         for(;itr != vec.end();itr++)

          cout<<*itr<<" ";

          cout<<endl;

          return ;

         }

    vec.push_back(n); // 典型的背包问题

    FindSum(m-n,n-1,vec); //放入一个元素 在剩下的元素满足剩下的要求

    vec.pop_back();//不放入当期的元素  在剩下的元素满足所有的要求

    FindSum(m,n-1,vec);

    }

int main()

{

   vector<int> vec;

   FindSum(9,10,vec);

   system("pause");

   return 0;

    }

这是一个典型的背包问题,对于这类问题,主要的是理清思绪,是不是符合背包原则,然后找到合适的解。同时需要明白怎么处理边界问题,什么时候需要返回。如果sum为0了,说明已经有一个解了,如果没有合适的解,那么n或者m已经到了边界,比如M太大,不可能有解。也需要返回。


同时如果不理解背包问题,也是有办法解决的,不就是从一个数组中挑选一些元素么,只不过挑选的元素个数不同,像不像从一个数列的所有组合中找到符合条件的数列,也就是说,如果你知道怎么找一个数列的所有组合,那么从这些组合中挑选符合条件的即可,使用一个标志位数组,然后被标志的数据的和是否为要求的解即可。





两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数, 使其和为 m