Golf the Subset-Sum Problem

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

J, 57 53 51 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

Answer 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]

Answer 5

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.

Answer 6

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).

Answer 7

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.

Answer 8

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);
    }
}