13
\$\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\$
  • 5
    \$\begingroup\$ Related, possibly a dupe. \$\endgroup\$ – Giuseppe Jan 15 '18 at 1:40
  • \$\begingroup\$ I think this is a dupe but I would rather close the older one because it is outdated. \$\endgroup\$ – Sriotchilism O'Zaic Jan 15 '18 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 '18 at 1:59
  • \$\begingroup\$ I was intending to allow for floating points, yes \$\endgroup\$ – soapergem Jan 15 '18 at 2:14
  • 13
    \$\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 '18 at 2:22

14 Answers 14

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\$
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\$
  • 7
    \$\begingroup\$ Not one but two reduces? I've got to upvote this. \$\endgroup\$ – Neil Jan 15 '18 at 9:59
  • 1
    \$\begingroup\$ @Neil The lesser known "reduceMapReduce" \$\endgroup\$ – Lord Farquaad Jan 16 '18 at 15:12
6
\$\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\$
6
\$\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\$
  • \$\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 '18 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\$
  • \$\begingroup\$ Nice trick with m,. I had Êo à k@VnXx@gX for the same byte count. \$\endgroup\$ – Shaggy Jan 15 '18 at 8:35
5
\$\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\$
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\$
  • \$\begingroup\$ [1, 2, -1, 5] 0 --> [[],[2,0]] A set of non-empty lists is required. \$\endgroup\$ – FrownyFrog Jan 15 '18 at 4:48
  • \$\begingroup\$ @FrownyFrog Fixed \$\endgroup\$ – Οurous Jan 15 '18 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\$
  • \$\begingroup\$ [1, 2, -1, 5]#0 --> [[],[0,2]] A set of non-empty lists is required. \$\endgroup\$ – FrownyFrog Jan 15 '18 at 8:23
  • \$\begingroup\$ @FrownyFrog Thanks! Fixed. \$\endgroup\$ – Cristian Lupascu Jan 15 '18 at 8:28
3
\$\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\$
  • \$\begingroup\$ 12 bytes \$\endgroup\$ – user202729 Jan 15 '18 at 2:26
  • \$\begingroup\$ @user202729 Cool, thanks! \$\endgroup\$ – HyperNeutrino Jan 15 '18 at 2:30
  • 1
    \$\begingroup\$ -1 byte: The is unnecessary if you use ç rather than Ç. \$\endgroup\$ – Jonathan Allan Jan 15 '18 at 14:13
  • \$\begingroup\$ @JonathanAllan o good catch thanks! \$\endgroup\$ – HyperNeutrino Jan 15 '18 at 14:17
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\$
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\$

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

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