14
\$\begingroup\$

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!

\$\endgroup\$
7
  • 6
    \$\begingroup\$ Related, possibly a dupe. \$\endgroup\$
    – Giuseppe
    Jan 15, 2018 at 1:40
  • \$\begingroup\$ I think this is a dupe but I would rather close the older one because it is outdated. \$\endgroup\$
    – Wheat Wizard
    Jan 15, 2018 at 1:56
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – Arnauld
    Jan 15, 2018 at 1:59
  • \$\begingroup\$ I was intending to allow for floating points, yes \$\endgroup\$
    – soapergem
    Jan 15, 2018 at 2:14
  • 14
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Jan 15, 2018 at 2:22

15 Answers 15

9
\$\begingroup\$

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()
\$\endgroup\$
2
  • 7
    \$\begingroup\$ Not one but two reduces? I've got to upvote this. \$\endgroup\$
    – Neil
    Jan 15, 2018 at 9:59
  • 1
    \$\begingroup\$ @Neil The lesser known "reduceMapReduce" \$\endgroup\$ Jan 16, 2018 at 15:12
7
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ 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! \$\endgroup\$
    – cole
    Jan 15, 2018 at 6:30
5
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Nice trick with m,. I had Êo à k@VnXx@gX for the same byte count. \$\endgroup\$
    – Shaggy
    Jan 15, 2018 at 8:35
5
\$\begingroup\$

Clean, 104 102 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!

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ [1, 2, -1, 5]#0 --> [[],[0,2]] A set of non-empty lists is required. \$\endgroup\$
    – FrownyFrog
    Jan 15, 2018 at 8:23
  • \$\begingroup\$ @FrownyFrog Thanks! Fixed. \$\endgroup\$ Jan 15, 2018 at 8:28
4
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ 12 bytes \$\endgroup\$
    – DELETE_ME
    Jan 15, 2018 at 2:26
  • \$\begingroup\$ @user202729 Cool, thanks! \$\endgroup\$
    – hyper-neutrino
    Jan 15, 2018 at 2:30
  • 1
    \$\begingroup\$ -1 byte: The is unnecessary if you use ç rather than Ç. \$\endgroup\$ Jan 15, 2018 at 14:13
  • \$\begingroup\$ @JonathanAllan o good catch thanks! \$\endgroup\$
    – hyper-neutrino
    Jan 15, 2018 at 14:17
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 43 bytes

1-indexed.

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ hiᶠ⊇z+ʰXh~t?∧Xt comes out to the same length. \$\endgroup\$ Apr 16, 2019 at 3:54
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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