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

## Test Case

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

## Winning Criterion

This is , so the shortest code in bytes wins!

• 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 – DavidC 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. – DavidC 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


# Brachylog (2), 9 characters, language postdates challenge

{⊇.+0∧}ᵘb


Try it online!

{⊇.+0∧}ᵘb
⊇           subset
+0        that sums to 0
.  ∧       output the subset
{     }ᵘ     take all unique solutions
b    except the first (which is the empty solution)


## 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

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


## 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

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


# SWI-Prolog 84

This version prints the list, instead of trying to find an appropriate binding for a term in a predicate.

s([],O):-O=[_|_],sum_list(O,0),print(O).
s([H|T],P):-s(T,[H|P]).
s([_|T],O):-s(T,O).


### Input method

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


For the record, this is the version that finds a binding to satisfy the predicate:

s(L,O):-s(L,0,O),O=[_|_].
s([],0,[]).
s([H|T],S,[H|P]):-R is H+S,s(T,R,P).
s([_|T],S,O):-s(T,S,O).


### Input method

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


Previous revision contains an incomplete solution that didn't manage to remove empty set.

# Jelly, 6 bytes

ŒPḊSÐḟ


Try it online!

Just for completeness. Similar to Brachylog, Jelly also postdates the challenge, but by now, newer languages compete normally.

ŒP       Power set.
Ḋ      Dequeue, remove the first element (empty set).
Ðḟ   Filter out the subsets with truthy (nonzero)...
S       sum.


# 05AB1E, 5 bytes

æ¦ʒO>


Try it online!

If input must be space delimited, prepending # to this answer is the only change required.

## 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

• Rewriting the train as (<@":@(#~0=+/)@#"1 _~2#:@i.@^#) saves 4 characters. – algorithmshark Mar 9 '14 at 5:22

# Mathematica 62 57 38

Code

Input entered as integers in an array, 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.

# Stax, 8 bytesCP437

â±3╒yΣ╓à


Run and debug online!

## Explanation

Uses the unpacked version (9 bytes) to explain.

LS{|+!fmJ
L            Convert to list
S           Powerset
{   f      Filter with block
|+!       Sum is zero
mJ    Print each subset, joined by spaces

• Given a list of space-delimited integers as input; you are -- however -- taking a list as input. – Jonathan Frech Mar 3 '18 at 0:17
• Will fix at the cost of one byte. – Weijun Zhou Mar 3 '18 at 0:29

# Perl 6, 51 bytes

*.words.combinations.skip.grep(!*.sum)>>.Bag.unique


Try it online!

Returns a list of unique Bags that sum to 0. A Bag is a weighted Set.

### Explanation:

*.words                 # Split by whitespace
.combinations          # Get the powerset
.skip                  # Skip the empty list
.grep(!*.sum)          # Select the ones that sum to 0
>>.Bag                 # Map each to a weighted Set
.unique                # And get the unique sets


# J, 34 bytes

(a:-.~](<@#~0=+/)@#~[:#:@i.2^#)@".


Try it online!

## how

". converts the input to a list. then:

a: -.~ ] (<@#~ (0 = +/))@#~ [: #:@i. 2 ^ #
i.       NB. ints from 0 to...
2 ^ # NB. 2 to the input len
[: #:@         NB. converted to binary masks
] (             ) #~                NB. filter the input using
NB. us all subsets
(             )@                  NB. and to each one...
(  #~ (0 = +/))                   NB. return it if its sum is
NB. 0, otherwise make it
NB. the empty list.
(<@           )                   NB. and box the result.
NB. now we have our answers
NB. and a bunch of empty
NB. boxes, or aces (a:).
a: -.~                                     NB. remove the aces.


# Ruby, 110 bytes

a=gets.split.map &:to_i;b=[];(1...a.length).each{|c|a.permutation(c){|d|d.sum==0?b<<d:0}};p b.map(&:sort).uniq


Takes input from stdin as a list of numbers, e.g. 8 −7 5 −3 −2
Output for the sample input: [[-3, -2, 5]]