【题目描述】
你将得到一个整数n,请列出把整数n划分为若干个正整数的每一种方法.
【输入格式】
输入共1行;
第1行,1个正整数n;
【输出格式】
输出为若干行:
每行为用空格隔开的若干个正整数,为一种n划分为若干个正整数的方法,每组数按从小到大输出.
若两种方法中前k−1个数相同,则第k个数更小的在前.
【输入样例#1】
5
【输出样例#1】
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5
【数据说明】
1≤n≤20
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,se[22];
bool is=1;
void dfs(int left,int a)
{
if(left<=0)
{
for(int i=1;i<a-1;i++)
{
for(int j=i+1;j<a;j++)
{
if(se[i]>se[j])
{
is=0;
break;
}
}
}
if(is==0)
{
is=1;
memset(se,0,sizeof(se));
return ;
}
else
{
for(int i=1;i<a;i++)
{
cout<<se[i]<<' ';
}
cout<<endl;
}
is=1;
memset(se,0,sizeof(se));
}
else
{
for(int i=1;i<=left;i++)
{
se[a]=i;
dfs(left-i,a+1);
}
}
}
int main()
{
cin>>n;
dfs(n,1);
return 0;
}
测试数据:
输入
3
输出
1 1 1
0 2
3
预期
1 1 1
1 2
3
输入
6
输出
1 1 1 1 1 1
0 0 0 0 2
0 0 0 3
0 0 0 2
0 0 4
0 0 0 2
0 0 3
0 0 2
0 5
0 0 0 2
0 0 3
0 0 2
0 4
0 0 2
0 3
0 2
6
预期
1 1 1 1 1 1
1 1 1 1 2
1 1 1 3
1 1 2 2
1 1 4
1 2 3
1 5
2 2 2
2 4
3 3
6
输入
4
输出
1 1 1 1
0 0 2
0 3
0 2
4
预期
1 1 1 1
1 1 2
1 3
2 2
4
为神马不行??