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

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

题目的要求是给定正整数M，求所有和为M的正整数集合。

如M=5，

则输出:

1,1,1,1,1

1,2,2

2,3

这是一道很典型的搜索问题，可以采用递归+回溯的方法来解答。

需要注意的地方有两个：

首先是必须以递增的顺序搜索数组。

其次是要注意递归调用结束后的回退（rollback），

下面是我的答案。

时间复杂度为O(2^n)，试了一下M=50的时候，输出结果就是天文数字了。

[cpp]
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;
}

补充：软件开发 , C++ ,