打印整数划分结果

 

打印整数划分

时间限制：3000 ms  |  内存限制：65535 KB

难度：3

 

描述

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 
其中n1≥n2≥…≥nk≥1，k≥1。 
正整数n的这种表示称为正整数n的划分。求正整数n的不 
同划分个数。 
例如正整数6有如下11种不同的划分： 
6； 
5+1； 
4+2，4+1+1； 
3+3，3+2+1，3+1+1+1； 
2+2+2，2+2+1+1，2+1+1+1+1； 
1+1+1+1+1+1。 

 

输入

第一行是测试数据的数目M（1<=M<=10）。以下每行均包含一个整数n（1<=n<=10）。

输出

输出每组测试的划分，格式如上所示。

样例输入

1
6

样例输出 

　　      6
　　　　5+1
　　　　4+2，4+1+1
　　　　3+3，3+2+1，3+1+1+1
　　　　2+2+2，2+2+1+1，2+1+1+1+1
　　　　1+1+1+1+1+1

// 打印整数划分
#include <cstdio>
#include <iostream>

using namespace std;
int cnt, tot;
int a[100];

void fun(int n, int sum)
{
    if(sum == tot)     //注意这里的打印技巧
    {
        for(int i = 0; i < cnt-1; ++i)
            printf("%d+", a[i]);
        if(tot - a[0] == cnt-1)
            printf("%d\n", a[cnt-1]);
        else
            printf("%d,", a[cnt-1]);
        return;
    }
    for(int i = n; i > 0; --i)
    {
        if(sum + i <= tot)
        {
            a[cnt++] = i;
            fun(i, sum+i);//注意这里不是fun (n - i, sum+i),因为每次的划分结果都是从大到小排序的
                            //所以每次枚举的最大数不能大于上一次的值;
            cnt--;     //  记得这里要回溯
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        cnt= 0;
        scanf("%d", &tot);
        fun(tot, 0);
    }
    return 0;
}