1
$\begingroup$

Problem: Given a number $n,$ we want to find out the subsets of $\{1,2,\ldots,n\}$ that add up to the given number $n.$

Example: If $n=6,$ then the output is: $\{1,5\}, \{2,4\}, \{1,2,3\}.$

Can anyone suggest a program for this?

  • 0
    [Ordered partitions of an integer](http://math.stackexchange.com/q/117489/19341)...2012-04-05

2 Answers 2

1

First, if $N=6$, then the output should also include $\{{6\}}$.

Second, it's not clear whether you want to write a program that can do this, or whether you want to be directed to an already-existing program that can do it. If it's the former, it shouldn't be too hard. The largest number used has to be at least $(1/2)(\sqrt{8N+1}-1)$; let's call this quantity (after rounding up to an integer) $r$. So for each value of $n$ from $r$ to $N$, you compute, recursively, the partitions of $N-n$ into distinct parts less than $n$, and then stick $n$ into each of them.

E.g., for $N=11$, we get $r=5$, so first we compute the useful partitions of $N-r=6$, which are $\{{2,4\}}$ and $\{{1,2,3\}}$, and that gives us $\{{2,4,5\}}$ and $\{{1,2,3,5\}}$; then let $n=6$, $N-n=5$, partition 5 as $\{{5\}},\{{1,4\}},\{{2,3\}}$, so we have $\{{5,6\}},\{{1,4,6\}},\{{2,3,6\}}$; and so on.

  • 0
    The word "useful" was intended to take care of that: in the example, when we compute partitions of 6, we discard $\{{1,5\}}$ as not being useful because it would lead to $\{{1,5,5\}}$.2012-03-29
0

If Matlab suits you, you might have a look here: Partitions of an integer.