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 code-golf, so the shortest code wins!
JavaScript (ES6), 96 bytes

Takes input in currying syntax (list)(target).



a=&gt;s=&gt;a.reduce((b,_,x)=&gt;[...b,...b.map(y=&gt;[...y,x])],[[]]).filter(b=&gt;!b.reduce((p,i)=&gt;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=&gt;s=&gt;a.reduce((b,_,x)=&gt;[...b,...b.map(y=&gt;[...y,x])],[[]]).filter(b=&gt;!b.reduce((p,i)=&gt;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 =&gt; s =&gt;                 // given an array a[] of length N and an integer s
  a.reduce((b, _, x) =&gt;   // 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 =&gt;           //     all previous entries stored in y[]
        [...y, x]         //     followed by the new index x
      )                   //   leading to:
    ],                    //   [[]] -&gt; [[],[0]] -&gt; [[],[0],[1],[0,1]] -&gt; ...
    [[]]                  //   we start with a list containing an empty array
  )                       // end of reduce()
  .filter(b =&gt;            // step #2: filter the powerset
    !b.reduce((p, i) =&gt;   //   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()