一道算法题：求和为某正整数的所有正整数集合
应该是网易的一道题目？忘记在哪里看到的了。
题目的要求是给定正整数M，求所有和为M的正整数集合。
如M=5，
则输出:
1,1,1,1,1
1,2,2
2,3
这是一道很典型的搜索问题，可以采用递归+回溯的方法来解答。
需要注意的地方有两个：
首先是必须以递增的顺序搜索数组。
其次是要注意递归调用结束后的回退（rollback），
下面是我的答案。
时间复杂度为O(2^n)，试了一下M=50的时候，输出结果就是天文数字了。
void Print(int* B, int len){for(int i = 0; i < len; i++){printf("%d ", B[i]);}printf("\r\n");}void Helper(int s, int M, int* B, int idx, int sum){if(M <= 0)return;for( int i = s; i <= M ; i++){if( i + sum > M)break;B[idx] = i;idx ++;sum += i;if(sum == M){Print(B, idx);--idx;sum -= i;break;}else{Helper(i, M, B, idx, sum);}--idx;sum -= i;}}void Test(){int M = 10;int* B = new int[M];Helper(1, M, B, 0, 0);delete [] B;}int _tmain(int argc, _TCHAR* argv[]){Test();return 0;}