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

问题描述：
    输入两个整数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;
}

    上述方法二，思路确实很巧妙，但是有一定的限制，对于32位机器来说，只能枚举32个数。


    参数：http://blog.csdn.net/wuzhekai1985/article/details/6728657
    感谢作者的思路，多谢。