Generate combinations that add up to a target value
JavaScript (ES6), 96 bytes
Takes input in currying syntax (list)(target)
.
a=>s=>a.reduce((b,_,x)=>[...b,...b.map(y=>[...y,x])],[[]]).filter(b=>!b.reduce((p,i)=>p-a[i],s))
Test cases
This would fail on the 2nd test case if 4.8 and 10 were swapped because of an IEEE 754 precision error -- i.e. 14.8 - 4.8 - 10 == 0
but 14.8 - 10 - 4.8 != 0
. I think this is fine, although there may be a more relevant reference somewhere in meta.
let f =
a=>s=>a.reduce((b,_,x)=>[...b,...b.map(y=>[...y,x])],[[]]).filter(b=>!b.reduce((p,i)=>p-a[i],s))
console.log(JSON.stringify(f([1, 2, 1, 5])(8)))
console.log(JSON.stringify(f([4.8, 9.5, 2.7, 11.12, 10])(14.8)))
console.log(JSON.stringify(f([7, 8, 9, -10, 20, 27])(17)))
console.log(JSON.stringify(f([1, 2, 3])(7)))
Commented
a => s => // given an array a[] of length N and an integer s
a.reduce((b, _, x) => // step #1: build the powerset of [0, 1, ..., N-1]
[ ...b, // by repeatedly adding to the previous list b[]
...b // new arrays made of:
.map(y => // all previous entries stored in y[]
[...y, x] // followed by the new index x
) // leading to:
], // [[]] -> [[],[0]] -> [[],[0],[1],[0,1]] -> ...
[[]] // we start with a list containing an empty array
) // end of reduce()
.filter(b => // step #2: filter the powerset
!b.reduce((p, i) => // keeping only entries b
p - a[i], // for which sum(a[i] for i in b)
s // is equal to s
) // end of reduce()
) // end of filter()
J, 32 31 bytes
(=1#.t#])<@I.@#t=.1-[:i.&.#.1"0
Try it online!
1-[:i.&.#.1"0 Make a list of all masks
for the input list. We flip the bits
to turn the unnecessary (0...0)
into (1...1) that would be missing.
Define it as t.
(=1#.t#]) Apply the masks, sum and
compare with the target
<@I.@# Turn the matching masks into
lists of indices
Python 2, 110 bytes
lambda a,n:[b for b in[[i for i in range(len(a))if j&1<<i]for j in range(2**len(a))]if sum(a[c]for c in b)==n]
Try it online!