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 mathworld.com, 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;
}node;
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;
count++;
printf("%d. ",count);
while (a->parent!=NULL){
for (i=0;i<a->num;i++)
printf("%d ", a->level);
a = a->parent;
}
printf("n");
}
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);
return;
}else{
sum(tmp, level+1, this);
}
}
}
int main()
{
node *root = alloc();
printf("Enter a number : ");
scanf("%d",&n);
sum(0, 1, root);
return 0;
}