Generating all distinct partitions of a number

First, write a recursive algorithm that returns all partitions, including those that contain repeats.

Second, write an algorithm that eliminates partitions that contain duplicate elements.

EDIT:

You can avoid results with duplicates by avoiding making recursive calls for already-seen numbers. Pseudocode:

Partitions(n, alreadySeen)
 1. if n = 0 then return {[]}
 2. else then
 3.    results = {}
 4.    for i = 1 to n do
 5.       if i in alreadySeen then continue
 6.       else then
 7.          subresults = Partitions(n - i, alreadySeen UNION {i})
 8.          for subresult in subresults do
 9.             results = results UNION {[i] APPEND subresult}
10.    return results

EDIT:

You can also avoid generating the same result more than once. Do this by modifying the range of the loop, so that you only add new elements in a monotonically increasing fashion:

Partitions(n, mustBeGreaterThan)
1. if n = 0 then return {[]}
2. else then
3.    results = {}
4.    for i = (mustBeGreaterThan + 1) to n do
5.       subresults = Partitions(n - i, i)
6.       for subresult in subresults do
7.          results = results UNION {[i] APPEND subresult}
8.    return results

What you're trying to do doesn't make a lot of sense to me but here's how I would approach it.

First, I'd create a loop that iterates i from 1 to n - 1. In the first loop, you could add the partition 1, i. Then I'd go recursive using the value in i to get all the sub-partitions that can also be added to 1.

And then continue to 2, and so on.

You don't need recursion at all. The list of numbers is essentially a stack, and by iterating in order you ensure no duplicates.

Here's a version which shows what I mean (you tagged this C, so I wrote it in C. In C++ you could use a dynamic container with push and pop, and tidy this up considerably).

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

void partition(int part)
{
int *parts;
int *ptr;
int i;
int idx = 0;
int tot = 0;
int cur = 1;
int max = 1;

    while((max * (max + 1)) / 2 <= part) max++;

    ptr = parts = malloc(sizeof(int) * max);

    for(;;) {
        if((tot += *ptr++ = cur++) < part) continue;

        if(tot == part) {
            for(i = 0 ; i < ptr-parts ; i++) {printf("%d ",parts[i]);}
            printf("\n");
        }

        do {
            if(ptr == parts) {free(parts); return;}
            tot -= cur = *--ptr;
        } while(++cur + tot > part);
    }
}

int main(int argc, char* argv[])
{
    partition(6);
    return 0;
}