Generating all distinct partitions of a number

Question

I am trying to write a C code to generate all possible partitions (into 2 or more parts) with distinct elements of a given number. The sum of all the numbers of a given partition should be equal to the given number. For example, for input n = 6, all possible partitions having 2 or more elements with distinct elements are:

• 1, 5
• 1, 2, 3
• 2, 4

I think a recursive approach should work, but I am unable to take care of the added constraint of distinct elements. A pseudo code or a sample code in C/C++/Java would be greatly appreciated.

Thanks!

Edit: If it makes things easier, I can ignore the restriction of the partitions having atleast 2 elements. This will allow the number itself to be added to the list (eg, 6 itself will be a trivial but valid partition).

Answer 1

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