2010 年中興面試題
程式設計求解：
輸入兩個整數n 和m，從數列1，2，3.......n 中随意取幾個數,
使其和等于m ,要求将其中所有的可能組合列出來。
// 21 題遞歸方法
//copyright@ July && yansha
//July、yansha，updated。
#include<list>
#include<iostream>
using namespace std;
list<int>list1;
void find_factor(int sum, int n)
{
// 遞歸出口
if(n <= 0 || sum <= 0)
return;
// 輸出找到的結果
if(sum == n)
// 反轉list
list1.reverse();
for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
cout << *iter << " + ";
cout << n << endl;
}
list1.push_front(n); //典型的01 背包問題
find_factor(sum-n, n-1); //放n，n-1 個數填滿sum-n
list1.pop_front();
find_factor(sum, n-1); //不放n，n-1 個數填滿sum
int main()
int sum, n;
cout << "請輸入你要等于多少的數值sum:" << endl;
cin >> sum;
cout << "請輸入你要從1.....n 數列中取值的n：" << endl;
cin >> n;
cout << "所有可能的序列，如下：" << endl;
find_factor(sum,n);
return 0;
邏輯分析：
1、比起微軟，google，百度這些公司，中興的面試題還是略顯逗比的，并非是說難度上差異，而是中興的題目總是顯得不倫不類。本題其實就是考察數的組合，對于此類問題，通常手段都是遞歸，而我們的目标就在于找出遞歸式。
2、問題其實本質上就是0/1背包問題，對于每一個n，我們采用貪婪政策，先考察是否取n，如果取n，那麼子問題就變成了find(n-1,m-n)，而如果舍棄n，子問題則為find(n-1,m)。至此，我們利用DP思想找到了遞歸式（很多時候，所謂動态規劃，貪婪隻是一念之差）。
3、那麼，如何制定解的判定政策？我們知道，遞歸需要邊界條件，而針對背包問題，邊界條件隻有兩種，如果n<1或者m<1，那麼便相當于“溢出”，無法combo出m，而另一種可能就是在剩餘的n個裡恰好滿足m==n，即此時 背包剛好填充滿，輸出一組解單元。除此之外，再無其他。
C源碼：
注：我們設定flag背包，用來标注對應的n+1是否被選中，1表示被選中，0則表示未選中，每當滿足m==n時，則輸出一組解。程式容易産生邏輯bug的地方在于length的使用（讀者可以思考一下為何需要全局變量length，而不是直接使用n來代替for循環）。
