P2404 自然数的拆分问题

[# 自然数的拆分问题

题目描述

任何一个大于 $1$ 的自然数 $n$，总可以拆分成若干个小于 $n$ 的自然数之和。现在给你一个自然数 $n$，要求你求出 $n$ 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数 $n$。

输出格式

输出：若干数的加法式子。

样例 #1

样例输入 #1

7

样例输出 #1

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

提示

数据保证，$2\leq n\le 8$。]() 深度优先搜索：

#include<iostream>
#include<cstdio>
#include<algorithm>
const int N = 10;
int a[N];
bool st[N];
int n;

using namespace std;
void dfs(int u, int v, int w)//u:累加结果，v:数组下标，w:加的数。
{
	if (u == n)//当累加结果和给出值一致时，输出结果，结束。
	{
		for (int i = 1; i <= v - 2; i++)
		{
			cout << a[i] << '+';
		}
		cout << a[v-1] << endl;//防止多输出'+'号，以及0；
		return;
	}
	if (u > n) return;
	for (int i = w; i <= n - 1; i++)
	{
		a[v] = i;//第一个数为i:1+...
		u += i;
		dfs(u, v + 1, i);//递归
		a[v] = 0;
		u -= i;//复原现场。
	}
}
int main()
{
	cin >> n;
	dfs(0,1,1);














	return 0;
}