输入两个整数 n 和 m,从数列1,2,3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来
转载的文章,原链接http://www.cnblogs.com/pippo0725/articles/2046366.html
这道题的思路参考0-1背包:定义函数F(n,m)来求解这个问题,那么F(n,m)可以分解为两个子问题F(n-1,m)和F(n-1,m-n).
代码的亮点应该就是flag数组的使用,充分利用了递归的性质,只是很简单的一个数组就完成了所有组合的输出。在每次把flag[i]设置为1之后就进入递归,代表了将i放入背包,当退出递归函数的时候,肯定要将flag[i]赋为0,因为这时候i已经不在背包中了。