微軟等數據結構與算法面試100題 第二十一題

第二十一題
題目：
輸入兩個整數n 和m，從數列1，2，3.......n 中隨意取幾個數,
使其和等於m ,要求將其中所有的可能組合列出來.
 
分析：
本題目主要考察的是動態規劃知識點。和最長公共子序列題目比較相似，
遞歸方程為
                      / sumk(m-n,n-1)
sumk(m,n)=
                      \sum(m,n-1)
與最長公共子序列不同的是題目要求輸出所有可能的組合，這就要求遞歸的時候需要保存當前的狀態彈出操作，就像是馬走日問題一樣。
比較容易想到使用棧進行遍歷的，但是由於使用棧的話對於棧中元素的遍歷不太方便，反而使用list比較方便。
 
在這裡需要指出的是July給出的答案存在一點點問題，就是當m<n的時候沒有考慮到。
 
代碼：
[cpp]
#include<iostream> 
#include<list> 
using namespace std; 
 
void sumk(int sum_m, int n) 
{ 
    static list<int> indexStack; 
     
    if(n<1||sum_m<1)return; 
    if(sum_m>n) 
    { 
        indexStack.push_front(n); 
        sumk(sum_m-n,n-1); 
        indexStack.pop_front(); 
        sumk(sum_m,n-1); 
    } 
    else 
    { 
        cout<<sum_m<<" "; 
        for(list<int>::iterator iter = indexStack.begin();iter!=indexStack.end();++iter) 
            cout<<*iter<<" "; 
        cout<<endl; 
    } 
 
} 
 
void sumk_m(int sum_m, int n) 
{ 
    if(sum_m<=n) 
    { 
        cout<<sum_m<<endl; 
        sumk(sum_m,sum_m-1); 
    } 
    else 
    { 
        sumk(sum_m,n); 
    } 
 
} 
 
 
int main() 
{  www.2cto.com
     
    sumk_m(10, 12); cout<<endl; 
    sumk_m(10, 10); cout<<endl; 
    sumk_m(10, 9);  cout<<endl; 
 
    return 0; 
}