一道算法題：求和為某正整數的所有正整數集合

應該是網易的一道題目？忘記在哪裡看到的了。

題目的要求是給定正整數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; 
}