（简单回溯） 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;
}