可直接食用

#include <bits/stdc++.h>
using namespace std;
int ans[114514]={1},n;
void dfs(int pi,int sum,int last){
    if(n==sum&&pi!=1){
    	cout<<n<<"=";
    	for(int i=0;i<pi;i++)cout<<ans[i]<<(i==pi-1?"\n":"+");
    	return;
	}for(int i=last;i+sum<=n;i++){
		ans[pi]=i;
		dfs(pi+1,sum+i,i);
	}
}
int main(){
    cin>>n;
    dfs(0,0,1);
    return 0;
}

题意

自然数拆分

思路

从小到大递归+回溯可以避免出现这个情况:

7=1+1+1+1+1+2​

7=1+1+1+1+2+1​

代码

tips:不用输出 total !

#include<iostream>
using namespace std;
int a[1145141];
int n;
void dfs(int ceng,int sum,int last)//递归层数,和,上一个数字
{
	if(sum==n)//为指定值时
	{
		cout<<n<<"=";//输出
		for(int i=0;i<ceng;i++)
		{
			cout<<a[i]<<(i==ceng-1?"\n":"+");//三目运算的巧妙之处
		}
		return;//注意要返回
	}
	for(int i=last;i<n;i++)//从小到大递归+回溯
	{
		if(sum+i<=n)//要有个判断
		{
			a[ceng]=i;//设置值
			dfs(ceng+1,sum+i,i);//递归
			a[ceng]=0;//回溯
		}
	}
}
int main()
{
	cin>>n;//输入
	a[0]=1;//初始值
	dfs(0,0,1);//递归
	return 0;//完结散花
}

不用输出total！！！！！！！！！！！！！！！！！

#include<bits/stdc++.h>
using namespace std;
int arr[11000],t,ans,vis[11000];
void dfs(int n,int s,int last){
    if(last==n) return;
    if(s==0){
        cout<<n<<'=';
        for(int i=0;i<t;i++){
            if(i!=0)cout<<'+'<<arr[i];
            else cout<<arr[i];
        }
        cout<<'\n';
        ans++;
        return;
    }
    for(int i=last;i<=s;i++){
        arr[t++]=i;
        dfs(n,s-i,i);
        arr[--t]=0;
    }
}
int main(){
    int n;
    cin>>n;
    vis[0]=1;
    dfs(n,n,1);
    //printf("total=%d",ans);
    return 0;
}

#include<iostream>
using namespace std;
int n,cnt=0;
int out[100] = {1};

void dfs(int step,int sum)
{
	if (sum>n){
		return;
	}
	if (sum==n){
		cout << n << "=";
		for (int i=1;i<step-1;i++)cout << out[i] << "+";
		cout << out[step-1];
		cout << endl;
		cnt++;
		return;
	} 
	for (int i=out[step-1];i+sum<=n && i<n;i++){
		out[step]=i;
		//cout << i <<endl;
		dfs(step+1,sum+i);
	}
	
}

int main()
{
	cin >> n;
	dfs(1,0);
	//cout << cnt;
 } 

题意

把 $n$ 拆开，然后从小到大输出

PS：拆开不能和他本身相同（输出 n=n）

思路

我很好奇它为什么在 DP 的作业里

用回溯做，从小到大排序，所以不用用标记数组

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[10005] = {1};	// 前置为 1
void dfs(int u,int x){	// x 为还剩多少
	for (int i = a[u - 1];i <= x;i++){
		a[u] = i;
		if (x - i == 0 && i != n){	// 填完后看看够不够了
			printf("%d=",n);
			for (int i = 1;i < u;i++){
				printf("%d+",a[i]);
			}
			cout << a[u] << "\n";
			return;
		}
		dfs(u + 1,x - i);	// 不够就继续递归
	}
}
int main(int argc, char **argv){
	cin >> n;
	dfs(1,n);	// 从 1 开始
	return 0;
}

如果你觉得我做得不好，请在评论区@我（@[](/user/137)）

#include<bits/stdc++.h>
using namespace std;
int n;
int sum=0;
int a[10005]={1};
void dfs(int s,int r){
	if(s==0){
		cout<<n<<'=';
		for(int i=1;i<r-1;i++) if(a[i]) cout<<a[i]<<'+';
		cout<<a[r-1]<<"\n";
		sum++;
		return;
	}
	for(int i=a[r-1];i<=s;i++){
		if(i<n){
			a[r]=i;
			s-=i;
			dfs(s,r+1);
			s+=i;
		}
	}
}
int main(){
	system("color F1");
	cin>>n;
	dfs(n,1);
	return 0;
}

我还以为要输出total...

using namespace std;

int n;
int a[55];

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

void dfs(int rest, int m)
{
	//cout<<rest<<endl;
	for(int i = a[m - 1]; i <= rest; i++)
	{
		if(i <= rest)
		{
			a[m] = i;
			rest -= i;
			if(rest == 0)
			{
				print(m);
			}
			else 
			{
				dfs(rest, m + 1);
			}
			rest += i;
		}
	}
}
int main()
{
	cin >> n;
	a[0] = 1;
	cout << n << "=";
	dfs(n, 1);
	return 0;
}

整活呆马

#include<bits/stdc++.h>

#define Genshin int
#define Impact main
#define Start ()
#define kaka cin
#define hepingjingying cout
#define wangluogongzhu bool

using namespace std;

Genshin a[10001] = {1}, n;

void dfsy(Genshin s, Genshin t){
	if(s == 0){
		cout << n << "=";
		for(Genshin i = 1; i < t - 1; i++){
			if(a[i] != 0){
				hepingjingying << a[i] << "+";
			}
		}
		hepingjingying << a[t -1] << endl;
		return ;
	}
	for(Genshin i = a[t - 1]; i <= s; i++){
		if(i  < n){
			a[t] = i;
			s -= i;
			dfsy(s, t+1);
			s += i;
		}
	}
}

Genshin Impact Start{
	kaka >> n ;
	dfsy(n,1);
	return 0;
}

# AC呆马：

#include <iostream>
using namespace std;

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

void dfs(int s, int t)
{
	if(s == 0)
	{
		cout << n << "=";
		for(int i = 1; i < t-1; i++)
		{
			if(a[i] != 0)
				cout << a[i] << "+";
		}
		cout << a[t - 1] << endl;
		return;
	}
	for(int i = a[t-1]; i<= s; i++)
	{
		if(i < n)
		{
			a[t] = i;
			s -= i;
			dfs(s, t+1);
			s += i;
		}
	}
}

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