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
    You mean subsets of {1,2,...,N} right? Numbers don't have subsets.2012-03-27
  • 0
    What about $\[ 3,3 \]$? Are repetitions allowed?2012-03-27
  • 0
    So you don't want to include $[1,1,4]$ or $[3,3]$ then? In that case what you want is called "[partitions of an integer](http://enwp.org/Integer_partition) into distinct parts".2012-03-27
  • 0
    see here: [Partitions](http://en.wikipedia.org/wiki/Partition_%28number_theory%29)2012-03-27
  • 0
    Did I edit too much?2012-03-27
  • 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
    Thanks Gerry I am getting lost in recursion somewhere The integer partition problem gives u sets where elements are repeated also but my problem requires only distinct elements. Thanks, Anshul2012-03-28
  • 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.