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.
@yE./Q
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.
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.
f!.-TQ./E
Try it online: Demonstration
Got a little bit inspired by Fry.
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)
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>{@^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;
{grep *.sum==$^n,unique as=>~*,@^a.combinations}
\$\endgroup\$
{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.
->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.
: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.
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]
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
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
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
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
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;
Cases[{}⋃Subsets@#,s_/;Tr@s==#2]&
Cases[Fold[Append@@@Thread@{##}⋃#&,{{}},#],s_/;Tr@s==#2]&
~.@((=+/@>)#])]<@#~2#:@i.@^#
Generates the power set and filters it before removing duplicates.
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│
└─────┴───────┘
~.@((=+/@>)#])]<@#~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