Golf the Subset-Sum Problem

Question

Task

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 code-golf, so the shortest code in bytes wins!

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

Brachylog (2), 9 characters

{⊇.+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)

Answer 3

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

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.

Answer 6

05AB1E, 5 bytes

æ¦ʒO>

Try it online!

---

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

Answer 7

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.

Answer 8

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 9

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.

Answer 10

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

Answer 11

Stax, 8 bytes^CP437

â±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

Answer 12

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. using those masks, giving
                                           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.

Answer 13

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

Answer 14

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 15

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

Will add TIO link later.

Takes input from stdin as a list of numbers, e.g. 8 −7 5 −3 −2

How it works: It converts the input into an array of numbers. Gets all the permutations of the lengths from 1 to the array's length. It adds them to the output array if they sum to 0. It outputs the array without duplicates.

Output for the sample input: [[-3, -2, 5]]