Integer Partition (Recursive method)

#include <stdio.h>

int ans[100], t;

void integerPartition(int n, int p, int sum, int last)
{
    int i;

    if (sum == t)
    {
        printf("%d", ans[0]);
        for (i = 1; i < n; i++)
            printf(" + %d", ans[i]);
        printf("\n");
    }

    for (i = p; i >= 1; i--)
    {
        if (i <= last)
        {
            ans[n] = i;
            integerPartition(n+1, t-sum-i, sum+i, i);
        }
    }
}

int main(void)
{
    t = 6;
    integerPartition(0, t, 0, t);

    return 0;
}

上面這份Code用到四個參數...今天重寫一份以後簡約多了

#include <stdio.h>

int sol[101];

void integerPartition(int depth, int n)
{
    int i, L;

    if (n == 0)
    {
        printf("%d", sol[1]);
        for (i = 2; i < depth; i++)
            printf(" %d", sol[i]);
        printf("\n");
        return;
    }

    for (i = n; i >= 1; i--)
    {
        if (i <= sol[depth-1])
        {
            sol[depth] = i;
            integerPartition(depth+1, n-i);
        }
    }
}

int main(void)
{
    int n;

    while (scanf("%d", &n) == 1)
    {
        sol[0] = n+1;
        integerPartition(1, n);
    }

    return 0;
}

第三種寫法(改了幾個地方而已)

#include <stdio.h>

int sol[101];

void integerPartition(int depth, int n)
{
    int i, L;

    if (n < 0)
        return;
    if (n == 0)
    {
        printf("%d", sol[1]);
        for (i = 2; i < depth; i++)
            printf(" %d", sol[i]);
        printf("\n");
        return;
    }

    for (i = sol[depth-1]; i >= 1; i--)
    {
        sol[depth] = i;
        integerPartition(depth+1, n-i);
    }
}

int main(void)
{
    int n;

    while (scanf("%d", &n) == 1)
    {
        sol[0] = n+1;
        integerPartition(1, n);
    }

    return 0;
}