# Generate combinations that add up to a target value

## Challenge

Suppose you have a list of numbers, and a target value. Find the set of all combinations of your numbers which add up to the target value, returning them as list indices.

## Input and Output

The input will take a list of numbers (not necessarily unique) and a target summation number. The output will be a set of non-empty lists, each list containing integer values corresponding to the position of the values in the original input list.

## Examples

Input: values = [1, 2, 1, 5], target = 8
Output: [ [0,1,3], [1,2,3] ]

Input: values = [4.8, 9.5, 2.7, 11.12, 10], target = 14.8
Output: [ [0,4] ]

Input: values = [7, 8, 9, -10, 20, 27], target = 17
Output: [ [1,2], [0,3,4], [3,5] ]

Input: values = [1, 2, 3], target = 7
Output: [ ]


## Scoring

This is , so the shortest code wins!

• Related, possibly a dupe. – Giuseppe Jan 15 '18 at 1:40
• I think this is a dupe but I would rather close the older one because it is outdated. – Wheat Wizard Jan 15 '18 at 1:56
• Do floating point numbers really add something to the challenge? Not sure what the consensus is, but they will probably lead to precision errors in many languages. – Arnauld Jan 15 '18 at 1:59
• I was intending to allow for floating points, yes – soapergem Jan 15 '18 at 2:14
• Bleh, indices? I think this would be a nicer challenge returning a list of values, though I guess that raises a question with how repeated values are dealt with in subsets. – xnor Jan 15 '18 at 2:22

# Husk, 10 bytes

ηλfo=¹ṁ⁰tṖ


1-indexed. Try it online!

## Explanation

ηλfo=¹ṁ⁰tṖ  Inputs are a number n (explicit, accessed with ¹) and a list x (implicit).
η           Act on the incides of x
λ          using this function:
Ṗ   Take all subsets,
t    remove the first one (the empty subset),
f          and keep those that satisfy this:
ṁ⁰      The sum of the corresponding elements of x
o=¹        equals n.


This uses the latest addition to Husk, η (act on indices). The idea is that η takes a higher order function α (here the inline lambda function) and a list x, and calls α on the indexing function of x (which is ⁰ in the above program) and the indices of x. For example, ṁ⁰ takes a subset of indices, maps indexing to x over them and sums the results.

# 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,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()

• Not one but two reduces? I've got to upvote this. – Neil Jan 15 '18 at 9:59
• @Neil The lesser known "reduceMapReduce" – Lord Farquaad Jan 16 '18 at 15:12

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

# R, 85 84 bytes

function(l,k){N=combn
o={}
for(i in I<-1:sum(l|1))o=c(o,N(I,i,,F)[N(l,i,sum)==k])
o}


Try it online!

1-indexed.

combn usually returns a matrix, but setting simplify=F returns a list instead, allowing us to concatenate all the results together. combn(I,i,,F) returns all combinations of indices, and we take N(l,i,sum)==k as an index into that list to determine those which equal k.

# 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

• I feel like an explicit definition would help given all of the compositions, but unfortunately I only got the same length: 4 :'<@I.t#~x=1#.y#~t=.#:}.i.2^#y'. Try it online! – cole Jan 15 '18 at 6:30

# Japt, 14 bytes

m, à f_x!gU ¥V


Test it online!

### How it works

m, à f_x!gU ¥V   Implicit: U = input array, V = target sum
m,               Turn U into a range [0, 1, ..., U.length - 1].
à             Generate all combinations of this range.
f_          Filter to only the combinations where
x           the sum of
!gU        the items at these indices in U
¥V     equals the target sum.
Implicit: output result of last expression

• Nice trick with m,. I had Êo à k@VnXx@gX for the same byte count. – Shaggy Jan 15 '18 at 8:35

# Clean, 104102 98 bytes

import StdEnv
@n=[[]:[[i:b]\\i<-[0..n-1],b<- @i]]
?l n=[e\\e<-tl(@(length l))|sum(map((!!)l)e)==n]


Try it online!

• [1, 2, -1, 5] 0 --> [[],[2,0]] A set of non-empty lists is required. – FrownyFrog Jan 15 '18 at 4:48
• @FrownyFrog Fixed – Οurous Jan 15 '18 at 7:15

# Haskell, 76 bytes

x#t=[i|i<-tail$concat<$>mapM(\z->[[],[z]])[0..length x-1],t==sum[x!!k|k<-i]]


Try it online!

• [1, 2, -1, 5]#0 --> [[],[0,2]] A set of non-empty lists is required. – FrownyFrog Jan 15 '18 at 8:23
• @FrownyFrog Thanks! Fixed. – Cristian Lupascu Jan 15 '18 at 8:28

# Jelly, 11 bytes

ị³S=
JŒPçÐf


Try it online!

1-indexed. 4 bytes spent on returning indices rather than just the elements themselves.

-1 byte thanks to user202729
-1 byte thanks to Jonathan Allan

• 12 bytes – user202729 Jan 15 '18 at 2:26
• @user202729 Cool, thanks! – hyper-neutrino Jan 15 '18 at 2:30
• -1 byte: The ⁴ is unnecessary if you use ç rather than Ç. – Jonathan Allan Jan 15 '18 at 14:13
• @JonathanAllan o good catch thanks! – hyper-neutrino Jan 15 '18 at 14:17

# Wolfram Language (Mathematica), 43 bytes

1-indexed.

Pick[s=Subsets;s@Range@Tr[1^#],Tr/@s@#,#2]&


Try it online!

# Python 3, 144 bytes

lambda a,t:[[e for e,_ in x]for r in range(len(a))for x in combinations(list(enumerate(a)),r+1)if sum(y for _,y in x)==t]
from itertools import*


Try it online!

0-indexed. 44 bytes spent on returning indices rather than just the elements themselves.

# Brachylog, 18 15 bytes

hiᶠ⊇Shᵐ+~t?∧Stᵐ


Try it online!

-3 bytes because it now works as a generator. (It's probably possible to golf more, but working around the need to use indices is awkward.)

    S              The variable S
⊇               is a sublist of
ᶠ                the list of all
i                 pairs [element, index] from
h                  the first element of
the input;
hᵐ            the first elements of each pair
+           add up to
~t         the last element of
?        the input
∧       which isn't necessarily
S      S,
tᵐ    from which the last elements of each pair
are output.

• hiᶠ⊇z+ʰXh~t?∧Xt comes out to the same length. – Unrelated String Apr 16 '19 at 3:54

# Perl 6, 45 bytes

->\a,\b{grep {a[$_].sum==b},^a .combinations}  Test it ## Expanded: -> \a, # input list \b, # input target { grep { a[$_ ].sum # use the list under test as indexes into ｢a｣
==
b
},

^a              # Range upto ｢a｣ (uses ｢a｣ as a number)
.combinations   # get all of the combinations
}


# APL(NARS), 49 chars, 98 bytes

{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}


1-indexed; test:

  f←{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}
⎕fmt 8 f 1 2 1 5
┌2──────────────┐
│┌3────┐ ┌3────┐│
││2 3 4│ │1 2 4││
│└~────┘ └~────┘2
└∊──────────────┘
⎕fmt   14.8  f  4.8 9.5 2.7 11.12 10
┌1────┐
│┌2──┐│
││1 5││
│└~──┘2
└∊────┘
⎕fmt 17 f 7, 8, 9, ¯10, 20, 27
┌3──────────────────┐
│┌2──┐ ┌2──┐ ┌3────┐│
││4 6│ │2 3│ │1 4 5││
│└~──┘ └~──┘ └~────┘2
└∊──────────────────┘
⎕fmt 7 f 1 2 3
┌0┐
│0│
└~┘


comment:

{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}
⍳¯1+2*k←≢w←⍵         copy ⍵ in w, len(⍵) in k, return 1..2^(k-1)
n←{⍵⊤⍨k⍴2}¨                     traslate in binary each element of  1..2^(k-1) and assign the result to n
{∊⍵⊂w}¨                                for each binary element of n return the elemets of ⍵ in the place where there are the 1s
b←⍺=+/¨                                       sum them and see if the sum is ⍺, that binary array saved in b
∨/                                     :⍸¨b/n   if or/b, get all the elements of n that are 1s for array b, and calculate each all indexs
⋄⍬ else return Zilde as void set


# Pyth, 11 bytes

fqvzs@LQTyU


Try it online here, or verify all the test cases at once here.

fqvzs@LQTyUQ   Implicit: Q=input 1 (list of numbers), z=input 2 (target value, as string)
Trailing Q inferred
UQ   Generate range [0-<length of Q>)
y     Powerset of the above
f              Keep elements of the above, as T, when the following is truthy:
L T        Map elements of T...
@ Q         ... to the indicies in Q
s            Take the sum
q               Is the above equal to...
vz             z as an integer
Implicit print of the remaining results