Number partitioning algorithm

I didn’t find an algorithm on the internet for listing all non repeating partitions of a number(which is hard work). This took me about a week to finish because I didn’t find the core of this problem, number partitioning is described by an equation called theĀ Diophantine equation. Even though I saw this equation multiple times when browsing wikipedia, I didn’t use it to get the output I wanted, until today! Today(after seeing the same equation on, and caring to take a look) I found that it isn’t that hard if I use a recursive algorithm and record the results of it using a linked list(I kinda plugin linked lists mostly in to anything I code, specially algorithms!). Well, this is it!

This code is released under GPL v3.

#include <stdio.h>
#include <stdlib.h>

typedef unsigned int uint;
typedef struct anode{
    uint num;
    uint level;
    struct anode *parent;

uint n=0;

node* alloc()
    node *new = malloc(sizeof(node));
    new->num = 0;
    new->level = 0;
    new->parent = NULL;
    return new;
void backtrace(node *a)
    uint i;
    static uint count=0;
    printf("%d. ",count);
    while (a->parent!=NULL){
        for (i=0;i<a->num;i++)
            printf("%d ", a->level);
        a = a->parent;

void sum(uint total, uint level, node *owner)
    uint i;
    uint tmp = 0;
    node *this;

    if ( level > n ) return;
    for (i=0;i<=n;i++){

        tmp = total + level*i;
        this = alloc();
        this->parent = owner;
        this->num = i;
        this->level = level;

        if (tmp >= n){
            if (tmp == n) backtrace(this);
            sum(tmp, level+1, this);


int main()
    node *root = alloc();
    printf("Enter a number : ");

    sum(0, 1, root);
    return 0;