求K个数的和/寻找和为定值的多个数
题目：输入两个整数n和m，从数列1,2,3...n中随意取几个数，使其和等于m，要求列出所有的组合。
思路一：这个问题很像是之前的背包问题，就是将不同重量的物体放进一个背包中，背包所能承受的重量为sum，需要从n个物体中挑选出m个使其满足要求，并使得背包中所含的价值最大化。这个问题只需满足背包问题的部分条件，所以显得更加容易一些。
使用递归实现。
倒置字符串函数reverse：用于倒置字符串s中的各个字符的位置，如原来字符串中如果初始值为123456，则通过reverse函数可将其倒置为654321
问题其实本质上就是0/1背包问题，对于每一个n，我们采用贪婪策略，先考察是否取n，如果取n，那么子问题就变成了find(n-1,m-n)，而如果舍弃n，子问题则为find(n-1,m)。至此，我们利用DP思想（动态规划）找到了递归式（很多时候，所谓动态规划，贪婪只是一念之差）。
那么，如何制定解的判定策略？我们知道，递归需要边界条件，而针对背包问题，边界条件只有两种，如果n<1或者m<1，那么便相当于“溢出”，无法输出m，而另一种可能就是在剩余的n个里恰好满足m==n，即此时背包刚好填充满，输出一组解单元。除此之外，再无其他。
要注意到放n，和不放n个区别，即可!
//从数列1,2,3...n中随意取几个数，使其和等于m#include <iostream>
#include <list>
using namespace std;
list<int> list1;
void find_factor(int sum, int n)
{
//递归出口
if (n <= 0 || sum <= 0)
return;
//输出找到的数
if (sum == n)
{
list1.reverse();
for (list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
cout << *iter << "+";
cout << n << endl;
list1.reverse();
}
list1.push_front(n);
find_factor(sum - n, n - 1);//n放在里面
list1.pop_front();
find_factor(sum, n - 1);//n不放在里面
}
int main(void)
{
int sum, n;
cin >> sum >> n;
cout << "所有可能的序列，如下：" << endl;
//总和为sum,数列1,2,3...n
find_factor(sum, n);
return 0;
}