DFS2

不说了，还是DFS，萌新杀手(可能是因为我太菜了)

这次也是个模板题

自然数的拆分

链接看这里

我是真的菜，555

贴代码

#include<bits/stdc++.h>

using namespace std;

int n, tot, ans, uper;
int chose[1001] = {1};

int toprint(int bigg)//输出函数，个人喜好
{
	cout << n << '=';
	for (int i = 1; i < bigg - 1; i++)
	{
		cout << chose[i] << '+';
	}
	cout << chose[bigg - 1] << '\n';
	return 0;
}

int dfs(int np ,int tuper,int ns)//np接受拆分的数字位置，tuper接受每个位置的上限，这个和字典序有关，ns接受下一位枚举的起点，和字典序，防重合有关
{
	if (tot == n)
	{
		ans++;
		toprint(np);
		return 1;
	}
	for (int i = ns; i <= tuper; i++)
	{
		if (i == n)//这里很重要，防止单独输出一个n
		{
			continue;
		}
		chose[np] = i;
		tot += i;
		dfs(++np, tuper - i, i);
		tot -= i;
		np--;
	}
	return 0;
}

int main()
{
	cin >> n;
	dfs(1, n, 1);
	return 0;
}

这题值得注意的是，输出是按照字典序升序的，可以节省很多时间，其他的没啥可注意了，就是个普通的DFS，然而我写了一个半小时555…