自然數拆分II

對于大于1的自然數N (N<20) ，可以拆分成若幹個大于等于1的自然數之和。

例如，當N=6時，

6=6

6=5+1

6=4+2

6=4+1+1

6=3+3

6=3+2+1

6=3+1+1+1

6=2+2+2

6=2+2+1+1

6=2+1+1+1+1

6=1+1+1+1+1+1 

輸入

一個大于1的自然數N，N<20

輸出

所有的拆分情況.按由大到小的順序排列。

樣例輸入 

6

樣例輸出 

6 

5 1

4 2

4 1 1

3 3

3 2 1

3 1 1 1

2 2 2

2 2 1 1

2 1 1 1 1

1 1 1 1 1 1 

代碼

#include <bits/stdc++.h>

using namespace std;

int n,a[30];

void dfs(int r,int k)

{

        if(r==0)

        {

        for(int i=1;i<k;i++) cout<<a[i]<<" ";    

        cout<<endl;

        return;

        }

    for(int i=r;i>=1;i--)

    {

        if(i<=a[k-1])

            {

            a[k]=i;        

            dfs(r-i,k+1);

            }

    }           

}

int main()

{

    cin>>n;

    a[0]=n;

    dfs(n,1);

    return 0;

}