Partition function using dynamic programming in C

A partition of an integer is a way of writing it as a sum of positive integers. For example, partitions of 5 are:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

The order of numbers in a partition doesn’t matter. The number of partitions of a number \(n\) is given by the partition function \(p(n)\).

The first few values of \(p(n)\) are 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, … (A000041).

The partition function can be computed using a dynamic programming table-filling algorithm. Here it is in C:

#include <stdlib.h>

unsigned int partition(unsigned int n)
{
    unsigned int i, j;
    unsigned int result;
    unsigned int **table;

    if (n == 0) {
        return 1;
    }
   
    table = malloc((n + 1) * sizeof(unsigned int *));
    for (i = 0; i <= n; i++) {
        table[i] = malloc((n + 1) * sizeof(unsigned int));
    }

    for (i = 0;i <= n; i++) {
        table[i][0]=0;
    }
    for (i = 1; i <= n; i++) {
        table[0][i] = 1;
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (j > i) {
                table[i][j] = table[i][j - 1];
            }
            else {
                table[i][j] = table[i][j - 1] + table[i - j][j];
            }
        }
    }

    result = table[n][n];
    for (i = 0; i <= n; i++) {
        free(table[i]);
    }
    free(table);

    return result;
}

Example program:

#include <stdio.h>

int main(void) 
{
    unsigned int i;
    for (i = 0; i < 31; i++) {
        printf("%d\n",partition(i));
    }

    return 0;
}

Output: