（简单回溯） P2404 自然数的拆分问题

P2404 自然数的拆分问题

题目背景

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

题目描述

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

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#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

说明

用回溯做。。。。

n≤8

#include<stdio.h>
const int maxn=10;
int num[maxn],n;

void dfs(int x,int sum){
	if(sum>n) return;
	if(sum==n){
		for(int i=0;i<x;i++){
			if(i==x-1) printf("%d\n",num[i]);
			else printf("%d+",num[i]);
		}
		return ;
	}
	for(int i=1;i<n;i++){
		if(x!=0){
			if(i<num[x-1]) break;
		}
		num[x]=i;
		dfs(x+1,sum+i);
	}
	
}

int main(){
	scanf("%d",&n);
	dfs(0,0);
	return 0;
}