信奥赛CSP-J复赛集训（dfs专题）（12）：洛谷P2404：自然数的拆分问题

信奥赛CSP-J复赛集训（dfs专题-刷题题单及题解）（12）：洛谷P2404：自然数的拆分问题

题目描述

任何一个大于 1 1 1 的自然数 n n n，总可以拆分成若干个小于 n n n 的自然数之和。现在给你一个自然数 n n n，要求你求出 n 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 ≤ n ≤ 8 2\leq n\le 8 2≤n≤8。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
/*深搜思路： 
	输出的数是从小到大的
	设置一个参数记录本次填的数x，下一次直接从x开始枚举	
*/ 
int n,a[10]; 
void print(int k){
	for(int i=1;i<=k-2;i++){
		cout<<a[i]<<"+";
	}
	cout<<a[k-1]<<endl;
}
void dfs(int sum,int x,int k){//当前和sum，第k个位置从x开始枚举填写 
	if(sum==n){
		print(k);
		return;
	}
	if(sum>n) return;
	for(int i=x;i<=n-1;i++){//关键点：从x开始枚举 
		a[k]=i;//填数 
		dfs(sum+i,i,k+1); 
	}
}
int main(){
	cin>>n;
	dfs(0,1,1);
	
	return 0;
} 

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容