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!

  • 1
    \$\begingroup\$ 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? \$\endgroup\$ Commented Oct 10, 2012 at 4:03
  • \$\begingroup\$ @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 \$\endgroup\$
    – DavidC
    Commented Oct 10, 2012 at 7:15
  • 4
    \$\begingroup\$ @DavidCarraher, OP mixes terminology by talking about subsets of lists. \$\endgroup\$ Commented Oct 10, 2012 at 7:18
  • \$\begingroup\$ @PeterTaylor Thanks. Good point. \$\endgroup\$
    – DavidC
    Commented Oct 10, 2012 at 7:29

15 Answers 15


Brachylog (2), 9 characters


Try it online!

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

GolfScript, 41 characters

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

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


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)

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

  • \$\begingroup\$ Bravo! I came within a character... \$\endgroup\$
    – boothby
    Commented Oct 10, 2012 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.

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.


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

Golfed (ugly output):

from itertools import*
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*
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

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.

  • \$\begingroup\$ 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. \$\endgroup\$ Commented Oct 10, 2012 at 4:10
  • \$\begingroup\$ @KeithRandall: facepalm I was in a rush, so I didn't test my code. Thank you for pointing that out. \$\endgroup\$
    – beary605
    Commented Oct 10, 2012 at 5:01
  • \$\begingroup\$ You can probably save a character by doing from itertools import* \$\endgroup\$
    – Matt
    Commented Oct 10, 2012 at 11:32
  • \$\begingroup\$ actually the graves is shorthand for repr() \$\endgroup\$
    – gnibbler
    Commented Oct 10, 2012 at 23:06
  • \$\begingroup\$ @gnibbler: That would make a lot more sense when running `'hello'`. Thanks! \$\endgroup\$
    – beary605
    Commented Oct 10, 2012 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!

SWI-Prolog 84

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


Input method


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

s([H|T],S,[H|P]):-R is H+S,s(T,R,P).

Input method


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


Mathematica 62 57 38


Input entered as integers in an array, x.



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




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.


Jelly, 6 bytes


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.
  • \$\begingroup\$ input needs to be space delimited \$\endgroup\$
    – Razetime
    Commented May 11, 2021 at 14:48

05AB1E, 5 bytes


Try it online!

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


J, 57 53 51 49 characters

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


   >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
  • \$\begingroup\$ Rewriting the train as (<@":@(#~0=+/)@#"1 _~2#:@i.@^#) saves 4 characters. \$\endgroup\$ Commented Mar 9, 2014 at 5:22

Stax, 8 bytesCP437


Run and debug online!


Uses the unpacked version (9 bytes) to explain.

L            Convert to list
 S           Powerset
  {   f      Filter with block
   |+!       Sum is zero
       mJ    Print each subset, joined by spaces
  • \$\begingroup\$ Given a list of space-delimited integers as input; you are -- however -- taking a list as input. \$\endgroup\$ Commented Mar 3, 2018 at 0:17
  • \$\begingroup\$ Will fix at the cost of one byte. \$\endgroup\$ Commented Mar 3, 2018 at 0:29

J, 34 bytes


Try it online!


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

Perl 6, 51 bytes


Try it online!

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


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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.