vinicius.biz/blog

Dado um inteiro n, uma partição é uma maneira de escrever n como a soma de inteiros positivos. Somas que se diferem somente pela ordem dos números são consideradas as mesmas partições.

O código abaixo, em C, usa backtracking para imprimir a lista de partições de um inteiro lido do teclado.

Para n = 4, a saída é:

1 1 1 1
1 1 2
1 3
2 2
4 

Para n = 50, existem 204.226 partições (a 204.217ª é 13 37).

Download do código

#include <stdio.h>

void partition(int *n, int p, int *sum, int *k, int res[])
{
    int i, j;

    for (i=p; i<=*n; i++)
    {
        if ((*sum + i) <= *n)
        {
            *sum+= i;
            res[(*k)++] = i;
            if (*sum == *n)
            {
                for (j=0; j<*k; j++)
                {
                    printf(”%d “, res[j]);
                }
                printf(”\n”);
            }
            else
            {
                partition(n, i, sum, k, res);
            }
            *sum-= i;
            –(*k);
        }
        else
        {
            break;
        }
    }
}

int main()
{
    int sum, k, n, res[100];

    sum = k = 0;

    if (scanf(”%d”, &n) != EOF && n >= 1)
    {
        partition(&n, 1, &sum, &k, res);
    }

    return 0;
}