# Distinct subsets that sum to a given number

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.

-
Are duplicates allowed in the output? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Mar 18 at 0:19
What do you mean by "store"? Will input numbers always be positive integers? – Luis Mendo Mar 18 at 0:24
If a duplicate is generated, checked for uniqueness and then discarded, does that qualify for the bonus? The duplicate needs to be temporarily stored somehow. Perhaps the bonus rule could be more precise saying at most one duplicate can be present at any time? – Luis Mendo Mar 18 at 0:45
yes that is what i meant. i will add it. – zboyz Mar 18 at 0:48
Bonuses are generally discouraged in code-golf. I suggest that you decide on a single version of the challenge (bonus either required or not). – lirtosiast Mar 18 at 1:31

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

-

# Julia, 8982 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.

-

# 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)
``````
-
It seems a bit odd to claim the bonus when the integer partitions contain all of the subsets of the list that sum to the input, but I think that's the rather unclear bonus' fault... – FryAmTheEggman Mar 18 at 12:53

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

-

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

-
You can shave a couple bytes by using some routines instead of some of the methods, `{grep *.sum==\$^n,unique as=>~*,@^a.combinations}` – LockOpeners Mar 23 at 6:22

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

-

# 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

-

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

-

# 05AB1E, 8 bytes

Uses CP-1252 encoding. Code:

``````æÙvyO²Q—
``````

Try it online!

-

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

# 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

-

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

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

# 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))
)
), XMLTABLE(s)
WHERE ''||column_value=:n;
``````
-

# Mathematica, 33 bytes

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

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

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