一道算法题：求和为某正整数的所有正整数集合

应该是网易的一道题目？忘记在哪里看到的了。

题目的要求是给定正整数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;}