问题描述：
输入两个整数n和m，从数列1,2,3,.......n中随意去几个数，使其和等于m，要求将其中所有可能的组合列出来。
解决思路：
这个问题其实是背包问题的变形，给出两种解决方法。
解法一：
用递归，效率可能低了点。假设问题的解为F(n,m)，可分为两个子问题F(n-1,m-n)和F(n-1,m)。对于这两个问题递归求解，求解的过程中，如果找到了符合条件的数字组合，则打印出来。
解法二：
用循环，其实就是枚举所有组合。对于n，组合数应该为2^n。我们可以用一个数字i来表示组合。如果i = 5，其二进制形式为101，相应的组合为{1,3}。也就是说，二进制的每一位都表示一个数字，bit0代表数字1，bit1代表数字2，依次类推。当某位为1，表示选中了该位所表示的数字。
参考代码
-
#include <iostream>
-
using namespace std;
-
-
//函数功能：从数列1,2,3......n中随意取几个数，使其和等于m
-
//函数参数：n为当前最大值，m为剩余值，flag标记选中与否，len为flag的容量
-
//返回值： 无
-
void BagProlem_Solution1(int n, int m, int *flag, int len)
-
{
-
if(n < 1 || m < 1)
-
{
-
return;
-
}
-
-
if(n < m)
-
{
-
flag[n - 1] = 1;
-
BagProlem_Solution1(n - 1, m - n, flag, len); //选了n
-
flag[n - 1] = 0;
-
BagProlem_Solution1(n - 1, m, flag, len); //不选n
-
}
-
else
-
{
-
flag[m - 1] = 1; //n >= m,选中m即可（n = m）
-
for(int i = 0; i < len; i++)
-
{
-
if(flag[i] == 1)
-
{
-
cout << i + 1 << " ";
-
}
-
}
-
cout << endl;
-
flag[m - 1] = 0; //不选m，继续递归。比如n = 10, m = 8,求出{1,7}后，仍需继续，{1,3,4}和{1,2,5}都是解
-
BagProlem_Solution1(m - 1, m, flag, len);
-
}
-
}
-
-
//函数功能：从数列1,2,...n中随意选取几个数，使其和等于m
-
//函数参数：n为当前最大值，m为剩余值
-
//返回值： 无
-
void BagProlem_Solution2(int n, int m)
-
{
-
if(n < 1 || m < 1)
-
{
-
return;
-
}
-
if(n > m)
-
{
-
n = m;
-
}
-
-
int num = 1 << n; //枚举次数
-
for(int i = 1; i < num; i++)
-
{
-
int sum = 0;
-
int j, k;
-
for(j = i, k = 1; j != 0; j >>= 1, k++)
-
{
-
if(j & 1)
-
{
-
sum += k;
-
}
-
}
-
if(sum == m)//如果满足，打印结果
-
{
-
for(j = i, k = 1; j != 0; j >>= 1, k++)
-
{
-
if(j & 1)
-
{
-
cout << k << " ";
-
}
-
}
-
cout << endl;
-
}
-
}
-
}
-
-
int main()
-
{
-
int n, m;
-
cout<<"please enter n and m : ";
-
cin>>n>>m;
-
-
int *flag = new int[n];
-
for(int i = 0; i < n; i++)
-
{
-
flag[i] = 0;
-
}
-
BagProlem_Solution1(n, m, flag, n);
-
cout<<endl;
-
BagProlem_Solution2(n, m);
-
delete [] flag;
-
return 0;
- }
参数：http://blog.csdn.net/wuzhekai1985/article/details/6728657
感谢作者的思路，多谢。