Distinct subsets that sum to a given number

Question

Write a function that gets as an input a sorted array of positive numbers A, and an additional number n. The Task is to print out all distinct subsets of A, that sum to n.

Example:

Input:
A = [1,2,2,4,4]
n = 9

Output:
[1,2,2,4]
[1,4,4]

Bonus: -50% if your code doesn't store duplicate subset (the same subset but in different order) intern. The function will not store more than one duplicate subset in memory at a time.

Shortest code in bytes wins.

Answer 1

Pyth, 6

@yE./Q

Try it online

We get all of the subsets of the given list with yE, and then ./Q gets all of the integer partitions (lists of integers that add up to it) of the other input. @ Finds the intersection of the two sets.

Answer 2

Julia, 89 82 72 bytes

f(x,n)=partitions(n)∩foldl(vcat,[collect(combinations(x,i))for i=1:n])

This is a function that accepts an array and an integer and returns an array of arrays. It uses the same approach as FryAmTheEggman's clever Pyth answer and doesn't qualify for the bonus.

We get all combinations of the elements of x of size i for i in 1 to n, and take the intersection of this with the integer partitions of n. The resulting array is the set of combinations which are also partitions of n, i.e. those that sum to n.

Answer 3

Pyth, 9 - 50% = 4.5 bytes

f!.-TQ./E

Try it online: Demonstration

Got a little bit inspired by Fry.

Explanation:

f!.-TQ./E   implicit: Q = input list
      ./E   read a number from input and compute a list of partitions
f           filter for partitions T, which satisfy:
  .-TQ         remove the numbers in Q one by one from T
 !             check if the resulting list is empty 
               (and therefore the partition is a subset of Q)

Answer 4

JavaScript (ES6) 115

Using an hash table to store results, no duplicate is ever stored. But I doubt that this is what OP means for the bonus, so I will not claim it.

(A,n)=>[...Array(1<<A.length)].map((x,m)=>(x=A.filter((v,i)=>1<<i&m&&(t-=v,1),t=n),t||++s[x]),s={})&&Object.keys(s)

Less golfed

(A,n) =>
[...Array(1<<A.length)].map( // enumerate all the subsets (2^A.len)
  (x, // used as a local variable
   m  // current index, used as a bit mask
  ) => ( // build the current subset in x using bit mask
         // meanwhile, check if the elemnt sum is == n
    t = n,
    x = A.filter( (v,i) => 1<<i&m && (t-=v,1) ),
    t || ++s[x] // if the sum is n, add X to hash table (this avoid dups)
  ),
  s={}  // hash table init to empty
) && Object.keys(s) // return keys

Test

f=(A,n)=>[...Array(1<<A.length)].map((x,m)=>(x=A.filter((v,i)=>1<<i&m&&(t-=v,1),t=n),t||++s[x]),s={})&&Object.keys(s)

function go() {
  var a = A.value.match(/\d+/g)
  var n = +N.value
  O.textContent = f(a,n).join('\n')
}

go()

Array A <input id=A value='1 2 2 4 4'><br>
Value n <input id=N value=9><br>
<button onclick='go()'>Go</button>
<pre id=O></pre>

Answer 5

Perl 6, 50 bytes - 50% = 25

{@^a.combinations.unique(as=>~*).grep: *.sum==$^n}

Ungolfed

sub d (@a,$n) {
    @a.combinations.unique(as => ~*).grep: *.sum == $n
}

Perl 6 has a built in combinations operator (as well as one for permutations!). Both of these return a lazy list.

unique by itself would not return unique combinations, because technically they are not unique (they are equivalent) so we tell unique to compare them as strings (~$var coerces $var to a string, and * means Whatever)

Then we grep for Whatever.sum is equal to n; Result of last evaluated expression is returned by default

Lastly, if I don't define a signature, I can use $^var to refer to a passed variable. Alphabetical (Positional) order matters with these, as $^a is passed in before $^b;

Answer 6

Haskell, 54 * 1.0 76 bytes * 0.5 = 38

import Data.List
f n=foldl(\r e->r++[e|notElem e r,sum e==n])[].subsequences

Usage example: f 9 [1,2,2,4,4] -> [[1,2,2,4],[1,4,4]].

Brute force: check every subsequences, keep it if it has the right sum and has not been seen before. subsequences build the list of subsequences lazily, i.e. one after the other, so at most one new element is kept in memory together with all unique elements so far.

For reference the previous version with the built-in function to remove duplicates, which requires to build the whole list of subsequences in memory. 54 bytes, no bonus.

import Data.List
x#n=nub[y|y<-subsequences x,sum y==n]

Answer 7

MATL, 26 * 0.5 = 13

x{}FTinZ^!"0$G@)s=?2MVJX(u

Works with current version (14.0.0) of the language/compiler.

EDIT (June 10, 2016): The link below replaces J by JQ to adapt to recent changes in the language

Try it online!

Explanation

All possible subsets are tested to see if the sum is correct. For each subset, if the sum condition is satisfied the subset is stored in a (cell) array. Immediately after that, duplicates are removed (the only possible duplicate at this point is the newly added array, and in that case it is removed). So this gets the bonus.

x        % take number input implicitly. Delete (gets copied into clipboard G)
{}       % push empty cell array. Will be grown with the found subsets
FT       % push array [false, true]
in       % take array input. Push its length
Z^!      % Cartesian power. 2D array in which each column indicates (via
         % logical indexing) which elements of the input array form a
         % subset. This covers all possible subsets.
"        % for each column
  0$G    %   push the two inputs: number, then array
  @)     %   apply logical index to extract the current subset
  s      %   compute its sum
  =      %   are they equal?
  ?      %   if so
    2M   %     push the subset again
    V    %     convert numbers to string. Needed to test for uniqueness
    JX(  %     append that to the cell array that stores the subsets
    u    %     remove duplicates (the only possible duplicate is the
         %     newly appended subset)
         %   end if implicitly
         % end for each implicitly
         % display implicitly

Answer 8

Pyth, 8 bytes

{fqsTQyE

No bonus.

{ f         Unique elements of filter lambda T:
    q                     equals
      s T                        sum of T
      Q       First input
    y E    over all subsets of second input

Try it here.

Answer 9

Ruby, 73 bytes

->x,n{(1..n).flat_map{|i|x.combination(i).select{|c|eval(c*?+)==n}.uniq}}

This is a lambda function that accepts an array and an integer and returns an array of arrays. To call it, assign it to a variable, say f, and do f.call(x, n).

For each i from 1 to n, we get all combinations of size i of the elements of x, select those combinations c such that c sums to n, and take the unique elements.

Try it here

Answer 10

Brachylog, 39 bytes

:1fd.,{,.[L:N]hs?{_,0 .|b:2&I,?h+I=.}N}

Called with a list containing the list of numbers first and the value of the sum second.

Answer 11

05AB1E, 8 bytes

Uses CP-1252 encoding. Code:

æÙvyO²Q—

Try it online!

Answer 12

PHP, 162 - 50% = 81 bytes

function c($a,$n){$o=[];for(;++$i<pow(2,count($a));){$s=[];foreach($a as$x=>$e)if($i&pow(2,$x))$s[]=$e;if(array_sum($s)==$n&&!in_array($s,$o))$o[]=$s;}return$o;}

Without a powerset built in this was kind of a pain.

for(;++$i<pow(2,count($a));)                    #generate integers
foreach($a as$x=>$e)if($i&pow(2,$x))$s[]=$e;    #use integers to generate subsets
if(array_sum($s)==$n&&!in_array($s,$o))$o[]=$s; #conditionally add suset to output

the rest is just necessary initialisation and output

Answer 13

Jolf, 9 bytes, noncompeting

I had to do some bugfixes, ergo, invalid :( Try it here anyhow!

ψmψxd=uHj
 mψx      unique powerset of input array
ψ   d     filtered according to a function
     =uH   that tests if the sum of the member
        j  is the input number.

Test like

[1,2,2,4,4]

9

Answer 14

Oracle SQL 11.2, 199 bytes

SELECT DISTINCT s FROM(SELECT SYS_CONNECT_BY_PATH(TRUNC(i),'+')s FROM(SELECT''||COLUMN_VALUE+ROWNUM/100 i FROM XMLTABLE((:a)))START WITH i>0 CONNECT BY i>PRIOR i),XMLTABLE(s)WHERE''||column_value=:n;

Inputs are :
:a the array of positive numbers, formated like "1","2","3","3"
:n the target number

Un-golfed :

SELECT DISTINCT s 
FROM  (
        SELECT SYS_CONNECT_BY_PATH(TRUNC(i),'+')s 
        FROM   (
                 SELECT ''||COLUMN_VALUE+ROWNUM/100 i 
                 FROM   XMLTABLE((:a))
               )
        START WITH i>0 CONNECT BY i>PRIOR i
      ), XMLTABLE(s)
WHERE ''||column_value=:n; 

Answer 15

Mathematica, 33 bytes

Cases[{}⋃Subsets@#,s_/;Tr@s==#2]&

Mathematica, 57 bytes (-50%) = 28.5 bytes

Cases[Fold[Append@@@Thread@{##}⋃#&,{{}},#],s_/;Tr@s==#2]&

Answer 16

J, 28 bytes

~.@((=+/@>)#])]<@#~2#:@i.@^#

Generates the power set and filters it before removing duplicates.

Usage

Since J does not support ragged arrays, each subset is output within a box.

   f =: ~.@((=+/@>)#])]<@#~2#:@i.@^#
   9 f 1 2 2 4 4
┌─────┬───────┐
│1 4 4│1 2 2 4│
└─────┴───────┘

Explanation

~.@((=+/@>)#])]<@#~2#:@i.@^#  Input: n on LHS, A on RHS
                           #  Get the size of A
                   2      ^   Get 2^len(A)
                       i.@    Get the range [0, 1, ..., 2^len(A)-1]
                    #:@       Convert each to binary to get the masks for each subset
                 #~           Copy using each mask from A
               <@             Box each subset
      +/@>                    Unbox each and reduce using addition
     =                        Check which sums are equal to n, 1 if true else 0
            ]                 Get the list of boxed subsets
           #                  Copy only those whose sums are equal to n
~.@                           Remove duplicates and return