輸出1到N之間所有相加等於M的數字組合（背包問題）求相加為M的所有組合--微軟酷派經典面試題

問題：

輸入兩個整數 n 和 m，從數列1，2，3.......n 中 隨意取幾個數,使其和等於 m ,要求將其中所有的可能組合列出來.

分析：

解法：采用0-1背包的思想，使用遞歸方法：

　　當選擇n時，就用剩下的n-1填滿 m-n;

　　當不選擇n是，就用剩下的n-1填滿m；

　注意的是，當m=n時，即找到了符合條件的解。

#include
#include
using namespace std;

list list1;
int total=0;
void find(int sum, int n)
{
    //遞歸出口
    if(sum <= 0 || n <= 0)
        return;

    //輸出找到的結果
    if(sum == n)    //表示找到了一個值
    {
        list1.reverse();    //使輸出順序更規范
        for(list::iterator i = list1.begin(); i != list1.end(); i++)
            cout << *i <<" ";
        cout << n << endl;
        total++;
        list1.reverse();
    }

    list1.push_front(n);
    find(sum-n, n-1);    //如果放入n，則從剩余n-1個數中填滿sum-n
    list1.pop_front();
    find(sum, n-1);        //如果不放入n，從n-1個數中填滿sum
}

int main()
{
    int sum, n;
    cout<<"Please Input n&sum:"<>n>>sum;
    find(sum, n);
    cout<<"Total:"<