啊哈哈哈题解来喽！这写题解，多是一件霉事啊！

免责声明

本题解仅为个人观点，如与标准搜索模板有出入请忽略。标准答案请参考代老师33dai随后提交的程序答案。 什么？代老师还没发题解？那为什么不问问神奇海螺呢

对于DFS（深度优先搜索）的介绍在例5.2 组合的输出(题解 - 【例5.2】组合的输出 - 33OJ (33dai.cn)中有粗略讲解。故本题解建立在知晓DFS基础模板之上。如有不理解之处，请关闭题解并直接询问代老师，因为很有可能是我的题解写错了（雾）

# 【例5.3】自然数的拆分

题目内容：

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

那么很容易想到的，是进行n层循环，并且循环的起始条件是上一层循环的变量。比如下面这样的伪代码：

for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
		for(int k=j;k<=n;k++)
		cout<<i<<j<<k;

显然，并不知晓n的大小是多少，所以就无法得知写多少层循环。（翻找……）（揣摩……）（题目竟然不给n的范围，但是言而总之可能很大）所以，此时就需要用到递归算法的究极无敌plus升级SVIP super TI版高级形式：搜索与回溯

基本思路：

写一个dfs函数，如果加和等于n就输出，如果大于n则直接return，不符合条件，如果小于n就继续调用下一层循环。

其余的解释写在注释中

很坑的一点是，题目虽然给你的最后一行输出是total=，但是样例输出中并没有！所以不需要计数并输出！ （猜猜我怎么注意到这个问题的）

上代码！

#include
using namespace std;
int n=0,save[1000]={},k=0;  //n为输入，save存储结果，k存储位数 
void print(int k1)  //输出函数,k1为数组存储到了第几位 
{
	cout<<n<<"=";
	for(int i=1;i<=k1-1;i++)
		cout<<save[i]<<"+";
	cout<<save[k1]<<'\n';  //按照题目要求格式输出 
	//total++;
	return;
}
void dfs(int qs,int sum)  //深搜函数
//qs为本层搜索的起始数字，因为要求按照字典序
//可以理解为从小到大，所以不能每一层搜索都循环n次
//而是从上一层的i（也就是qs）开始循环到n 
{
	if(sum==n)  //如果加和等于n就输出 
	{
		print(k);  //k为当前数组的位数 
		return;
	}
	else if(sum>n) return;  //如果大于n则不符合条件，直接结束 
	else  //小于n 
	{
		for(int i=qs;i<n;i++)  //从qs循环到n达到字典序的效果 
		{
			k++;  //save数组的位数+1 
			save[k]=i;  //当前k位存储为i 
			dfs(i,sum+i);  //下一层循环，sum+i 
			save[k]=0;  //回溯，让当前位存储数字为0 
			k--;  //数组位数-1 
		}
	}
}
int main()
{
	cin>>n;
	dfs(1,0);  //搜索函数 
	//cout<<"total="<<total;
	return 0; 
}

#include <bits/stdc++.h>
using namespace std;
int n, cnt;
int ans[105];
//当前在决定第 now 个数选几
//上一个数选了 pre
//之前选的数之和是 sum
void dfs(int now, int pre, int sum)
{
    if (sum == n)
    {
        if (now == 2)
            return;
        cout << n << "=";
        for (int i = 1; i <= now - 1; i++)
        {
            cout << ans[i];
            if (i != now - 1)
                cout << "+";
        }
        cout << "\n";
        cnt++;
        return;
    }
    for (int i = pre; i <= n - sum; i++)
    {
        ans[now] = i;
        dfs(now + 1, i, sum + i);
    }
}
int main()
{
    cin >> n;
    dfs(1, 1, 0);
    return 0;
}

自然数的拆分！

需要注意：当长度是1的时候不输出，且按照规律每一位应大于等于前一位

#include<bits/stdc++.h>
using namespace std;
int n,cnt,ans[100000];
void dfs(int res,int las)
{
	if(res==0&&cnt!=1)//长度大于1，输出 
	{
		cout<<n<<"=";
		for(int i=1;i<=cnt;i++)
		{
			if(i!=1)cout<<"+"<<ans[i];
			else cout<<ans[i];
		}
		cout<<endl;
		return ;
	}
	for(int i=las;i<=res;i++)//搜索 
	{
		cnt++;
		ans[cnt]=i;
		dfs(res-i,i);
		cnt--;
	}
}
int main()
{
	cin>>n;
	dfs(n,1);
	return false; 
}