Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
Are duplicates allowed in the output? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Mar 18 at 0:19
1  
What do you mean by "store"? Will input numbers always be positive integers? – Luis Mendo Mar 18 at 0:24
2  
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
1  
yes that is what i meant. i will add it. – zboyz Mar 18 at 0:48
8  
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

15 Answers 15

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.

share|improve this answer

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.

share|improve this answer

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)
share|improve this answer
    
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>

share|improve this answer

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;

share|improve this answer
    
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

MATL, 26 * 0.5 = 13

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

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

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
share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

05AB1E, 8 bytes

Uses CP-1252 encoding. Code:

æÙvyO²Q—

Try it online!

share|improve this answer

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]
share|improve this answer

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

share|improve this answer

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
share|improve this answer

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; 
share|improve this answer

Mathematica, 33 bytes

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

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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