PTA 自然数拆分问题

题目描述：

一个整数N(N > 1)可以拆分成若干个大于等于1的自然数之和，请你输出所有不重复的拆分方式。

若满足集合A=B，则称这两种拆分方式是重复的。

例如 5 = 3 + 2 和 5 = 2 + 3, 就是重复的拆分方式。

输入格式:

一个正整数N（1 ≤ N ≤ 52）

输出格式:

按照拆分方案的字典序由小到大，输出所有方案，请参考输出样例

输入样例:

6

输出样例:

6=1+1+1+1+1+1
6=1+1+1+1+2
6=1+1+1+3
6=1+1+2+2
6=1+1+4
6=1+2+3
6=1+5
6=2+2+2
6=2+4
6=3+3
6=6

算法思想：

（参考洛谷P2404 自然数的拆分问题）
以拆分4为例，说明拆分的方法：
对于每个分支，父节点<=子节点<=当前被拆分数（为了满足字典序要求）
例如：4被拆分为1后，被拆分数变为3；4被拆分为1+1后，被拆分数变为2。

参考代码：

#include<bits/stdc++.h> 
using namespace std;

int a[52]={1},n;

void print(int num){
    cout << n << "=";
    for(int i=1;i<num;i++){
        cout << a[i] << "+";
    }
    cout << a[num] << endl;
}

void dfs(int cur,int num){
//cur为当前被拆分数, num为当前分支子节点的个数 

    for(int i=a[num-1];i<=cur;i++){//父节点<=子节点<=当前被拆分数 
        if(i==n) continue;//拆分数是被拆分数自身
        a[num]=i;//保存当前拆分的数i
        cur-=i;//拆分出i后,被拆分数进行更新 
        if(cur==0)//拆分结束,输出结果 
            print(num);
        else//递归,进行下一次拆分 
            dfs(cur,num+1);
        cur+=i;//回溯,刚才减去i,现在再加上i,分析其他情况 
    }

}

int main(){
    std::ios::sync_with_stdio(false);
    //cout超时,这里加速一下
    cin >> n;
    dfs(n,1);    
    cout << n << "=" << n; 
    return 0;    
}

代码分析：

可能是因为刚接触到回溯法，更可能是因为自己还太弱了（QAQ），看了好多大佬自然数拆分（回溯法）的题解也没完全弄懂逻辑，自己用数据模拟了几遍才逐渐清楚。

另外，这道题和洛谷上的还有些区别，可以看看洛谷上的题解找找思路。
题解 P2404 【自然数的拆分问题】
P2404 自然数的拆分问题