Golf the Subset-Sum Problem

Given a list of space-delimited integers as input, output all unique non-empty subsets of these numbers that each subset sums to 0.

For example:

Input: `8 −7 5 −3 −2`
Output: `-3 -2 5`

Language of your choice - shortest possible code.

-
 Do we have to worry about uniqueness if the input contains non-unique numbers? In other words, how many results do I have to print for the input `3 3 -3 -3`? – Keith Randall Oct 10 '12 at 4:03 @Keith. By convention, sets consist of distinct elements that appear at most once. Multisets can have elements that appear more than once. en.wikipedia.org/wiki/Multiset – David Carraher Oct 10 '12 at 7:15 @DavidCarraher, OP mixes terminology by talking about subsets of lists. – Peter Taylor Oct 10 '12 at 7:18 @PeterTaylor Thanks. Good point. – David Carraher Oct 10 '12 at 7:29

GolfScript, 41 characters

``````~][[]]\{`{1\$+\$}+%}%;(;.&{{+}*!},{" "*}%n*
``````

If you do not care about the specific output format you can shorten the code to 33 characters.

``````~][[]]\{`{1\$+\$}+%}%;(;.&{{+}*!},`
``````

Example (see online):

``````> 8 -7 5 -3 -2 4
-3 -2 5
-7 -2 4 5
-7 -3 -2 4 8
``````
-

Python, 119 chars

``````def S(C,L):
if L:S(C,L[1:]);S(C+[L[0]],L[1:])
elif sum(map(int,C))==0and C:print' '.join(C)
S([],raw_input().split())
``````

Enumerates all 2^n subsets recursively and checks each one.

-
 Bravo! I came within a character... – boothby Oct 10 '12 at 18:03

J, 575351 49 characters

``````>a:-.~(#:@i.@(2&^)@#<@":@(#~0=+/)@#"1 _])".1!:1[1
``````

Usage:

``````   >a:-.~(#:@i.@(2&^)@#<@":@(#~0=+/)@#"1 _])".1!:1[1
8 _7 5 _3 _2 4
5 _3 _2
_7 5 _2 4
8 _7 _3 _2 4
``````
-

Python, 120

I'm a character worse than Keith's solution. But... this is too close to not post. One of my favorite features of code-golf is how dissimilar similar-length solutions can be.

``````l=raw_input().split()
print[c for c in[[int(j)for t,j in enumerate(l)if 2**t&i]for i in range(1,2**len(l))]if sum(c)==0]
``````
-

Mathematica 62 57 38

Code

Input entered as integers in a grid, stored in `x`.

``````x
``````

``````Grid@Select[Subsets@x[[1, 1]], Tr@# == 0 &]
``````

Output

Explanation

`x[[1, 1]]` converts the input to a list of integers.

`Subsets` generates all subsets from the integers.

`Select....Tr@# == 0` gives all those subsets that have a total equal to 0.

`Grid` formats the selected subsets as space-separated integers.

-

SWI-Prolog 90

The empty subset is still there, though. I have no idea how to get rid of it.

``````:-[library(clpfd)].
s([],0,[]).
s([_|T],S,O):-s(T,S,O).
s([H|T],S,[H|P]):-S#=H+R,s(T,R,P).
``````

Input method

``````s([8,-7,5,-3,-2,4],0,O).
``````
-

Python (128 137 136)

Damn you, `itertools.permutations`, for having such a long name!

Brute force solution. I'm surprised it's not the shortest: but I guess `itertools` ruins the solution.

Ungolfed:

``````import itertools
initial_set=map(int, input().split())
ans=[]
for length in range(1, len(x)+1):
for subset in itertools.permutations(initial_set, length):
if sum(subset)==0:
ans+=str(sorted(subset))
print set(ans)
``````

Golfed (ugly output):

``````from itertools import*
x=map(int,input().split())
print set(`sorted(j)`for a in range(1,len(x)+1)for j in permutations(x,a)if sum(j)==0)
``````

Golfed (pretty output) (183):

``````from itertools import*
x=map(int,input().split())
print `set(`sorted(j)`[1:-1]for a in range(1,len(x)+1)for j in permutations(x,a)if sum(j)==0)`[5:-2].replace("'","\n").replace(",","")
``````

`import itertools as i`: importing the itertools module and calling it `i`

`x=map(int,input().split())`: seperates the input by spaces, then turns the resulting lists' items into integers (`2 3 -5` -> `[2, 3, -5]`)

set(`sorted(j)`for a in range(1,len(x)+1)for j in i.permutations(x,a)if sum(j)==0):
Returns a list of all subsets in `x`, sorted, where the sum is 0, and then gets only the unique items
(`set(...)`)

The graves (`) around `sorted(j)` is Python shorthand for `repr(sorted(j))`. The reason why this is here is because sets in Python cannot handle lists, so the next best thing is to use strings with a list as the text.

-
 I'm confused about how you're getting integers instead of strings. `split()` makes a list of strings, but then later you're calling `sum` on the subsets of that split. – Keith Randall Oct 10 '12 at 4:10 @KeithRandall: facepalm I was in a rush, so I didn't test my code. Thank you for pointing that out. – beary605 Oct 10 '12 at 5:01 You can probably save a character by doing `from itertools import*` – Matt Oct 10 '12 at 11:32 actually the graves is shorthand for `repr()` – gnibbler♦ Oct 10 '12 at 23:06 @gnibbler: That would make a lot more sense when running `'hello'`. Thanks! – beary605 Oct 10 '12 at 23:51
show 1 more comment

C# – 384 characters

OK, functional-style programming in C# is not that short, but I love it! (Using just a brute-force enumeration, nothing better.)

``````using System;using System.Linq;class C{static void Main(){var d=Console.ReadLine().Split(' ').Select(s=>Int32.Parse(s)).ToArray();foreach(var s in Enumerable.Range(1,(1<<d.Length)-1).Select(p=>Enumerable.Range(0,d.Length).Where(i=>(p&1<<i)!=0)).Where(p=>d.Where((x,i)=>p.Contains(i)).Sum()==0).Select(p=>String.Join(" ",p.Select(i=>d[i].ToString()).ToArray())))Console.WriteLine(s);}}
``````

Formatted and commented for more readability:

``````using System;
using System.Linq;

class C
{
static void Main()
{
// read the data from stdin, split by spaces, and convert to integers, nothing fancy
var d = Console.ReadLine().Split(' ').Select(s => Int32.Parse(s)).ToArray();
// loop through all solutions generated by the following LINQ expression
foreach (var s in
// first, generate all possible subsets; well, first just their numbers
Enumerable.Range(1, (1 << d.Length) - 1)
// convert the numbers to the real subsets of the indices in the original data (using the number as a bit mask)
.Select(p => Enumerable.Range(0, d.Length).Where(i => (p & 1 << i) != 0))
// and now filter those subsets only to those which sum to zero
.Where(p => d.Where((x, i) => p.Contains(i)).Sum() == 0)
// we have the list of solutions here! just convert them to space-delimited strings
.Select(p => String.Join(" ", p.Select(i => d[i].ToString()).ToArray()))
)
// and print them!
Console.WriteLine(s);
}
}
``````
-