Given a list of space-delimited integers as input, output all unique non-empty subsets of these numbers that each subset sums to 0.
Input: 8 −7 5 −3 −2
Output: -3 -2 5
This is code-golf, so the shortest code in bytes wins!
{⊇.+0∧}ᵘb
{⊇.+0∧}ᵘb
⊇ subset
+0 that sums to 0
. ∧ output the subset
{ }ᵘ take all unique solutions
b except the first (which is the empty solution)
~][[]]\{`{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
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.
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]
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.
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
from itertools import*
\$\endgroup\$
repr()
\$\endgroup\$
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);
}
}
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).
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).
s([8,-7,5,-3,-2,4],O).
Previous revision contains an incomplete solution that didn't manage to remove empty set.
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.
ŒPḊSÐḟ
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.
æ¦ʒO>
If input must be space delimited, prepending # to this answer is the only change required.
>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
(<@":@(#~0=+/)@#"1 _~2#:@i.@^#) saves 4 characters.
\$\endgroup\$
Commented
Mar 9, 2014 at 5:22
â±3╒yΣ╓à
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.
\$\endgroup\$
Commented
Mar 3, 2018 at 0:17
(a:-.~](<@#~0=+/)@#~[:#:@i.2^#)@".
". 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.
*.words.combinations.skip.grep(!*.sum)>>.Bag.unique
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
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]]
3 3 -3 -3? \$\endgroup\$