First question here, don't yell at me if this is a duplicate or a bad challenge.


I thought of this challenge myself, and it seems to be a good basic puzzle for beginner code-golfers. It also might help me decide which code-golfing language to learn.


Given an array of integers that are less than or equal to n, output or return the minimum number of numbers from the array that sum up to exactly n.

You can choose to write a function or a full program.


You can safely assume 0 <= n < 2^31.

Take an array or list of any kind (vector for C++ or Java's LinkedList are allowed), along with n and an optional parameter length, which specifies the length of the array.

You can also take the input as a space-separated string, separated from n by either a comma or a space:

1 5 7 3 7 3 6 3 2 6 3,10

1 5 7 3 7 3 6 3 2 6 3 10

if it is easier.


Output, or return the minimum number of numbers from the array that sum up to exactly n. Using the above example:

1 5 7 3 7 3 6 3 2 6 3,10

Your program should print:


because the minimum number of numbers that sum up to 10 is 2 (7 and 3).

In the case that there is no solution, print or return either a negative, 0, "No solution" (though that would not be smart), (as suggested), or any other falsy value, with the exception of an empty string.

Example Input and Output


1 5 7 3 7 3 6 3 2 6 3,10
143 1623 1646 16336 1624 983 122,18102
5 6 9,12




This is code-golf, so shortest code in bytes wins.

The top answer will be accepted on Christmas.

  • \$\begingroup\$ I've edited your spec, because we usually allow the same I/O methods for functions and programs; see the consensus here. Feel free to roll back if you disagree. \$\endgroup\$
    – lirtosiast
    Commented Dec 10, 2015 at 1:16
  • \$\begingroup\$ May we output false for cases with no solutions? \$\endgroup\$ Commented Dec 10, 2015 at 2:09
  • \$\begingroup\$ @ETHproductions Sure, will add that. \$\endgroup\$ Commented Dec 10, 2015 at 2:09
  • \$\begingroup\$ Do you consider empty output falsey, since the empty string is falsey in Pyth? \$\endgroup\$
    – lirtosiast
    Commented Dec 10, 2015 at 2:14
  • \$\begingroup\$ @ThomasKwa I don't like empty string outputs, but you can include that as "if x was allowed..." in your answer... \$\endgroup\$ Commented Dec 10, 2015 at 2:18

11 Answers 11


Pyth, 12 11 bytes


This takes n as the first line of input and the list on the second line.

lhafqsTQyEY     (Implicit: Q = 1st line of input; E = 2nd line)
         E      The list
        yE      Powerset (sorted by increasing length; empty set first)
   f            Filter by lambda T:
     sT         sum(T)
    q                  ==
       Q                  Q
   fqSTQyE      Sublists that sum to Q, sorted by increasing length
  a       Y     append an empty array (in case none match)
lh              take the length of the first element (0 for empty array)

Try it here.

  • 1
    \$\begingroup\$ Your code and your explanation don't match. \$\endgroup\$
    – isaacg
    Commented Dec 10, 2015 at 2:43
  • \$\begingroup\$ @isaacg Now fixed. \$\endgroup\$
    – lirtosiast
    Commented Dec 10, 2015 at 5:24

Japt, 30 21 18 bytes

Turns out there was a much more efficient method. ;)

Uà f_x ¥V} ml n- g

Test it online! (Note: n- has been changed to n@X-Y} for compatibility reasons)

This takes input as a space- or comma-separated array, followed by a number. Outputs undefined for test cases without solutions.

Uà f_  x ¥ V} ®   l} n- g
UàfmZ{Zx ==V} mZ{Zl} n- g

            // Implicit: U = input array, V = input integer
Uà fZ{   }  // Generate all possible combinations of U, then filter to only items Z where
Zx ==V      //   the sum of Z is equal to V.
mZ{Zl}      // Map each remaining combination to its length.
n-          // Sort by subtraction; smaller items end up in the front.
g           // Take the first item.
            // Implicit: output last expression

I can't believe I didn't think of this version when I originally wrote this...

Several optimizations have been made since then which come in handy here:

  • A U at the beginning of the program can usually be left out.
  • Ã is a shortcut for .
  • n now sorts numbers properly by default.

Each of these takes off a byte, for a total of 15:

à f_x ¥VÃml n g

Test it online!

  • \$\begingroup\$ That's 25 bytes, not 21. \$\endgroup\$ Commented Dec 10, 2015 at 3:14
  • 1
    \$\begingroup\$ @AlbertRenshaw Japt supports the IEC_8859-1 encoding, under which each of these characters is 1 byte. You can save this program as a IEC_8859-1-encoded text file, then upload it to the online interpreter. \$\endgroup\$ Commented Dec 10, 2015 at 3:18
  • \$\begingroup\$ Ah, nice! Thanks for informing me \$\endgroup\$ Commented Dec 10, 2015 at 3:19

Mathematica, 73 65 bytes


Pure function, returns if there is no solution.


Python 3, 128 bytes

This isn't as golfed as I'd like it to be, but I'll work on it later.

from itertools import*
def s(a,n):
 for i in range(len(a)):
  for j in permutations(a,i+1):
   if sum(j)==n:return i+1
 return 0

Mathematica, 45 bytes


CJam, 34 bytes


Try it online. The input format is the sum followed by the list of values, e.g.:

18102 [143 1623 1646 16336 1624 983 122]

Note that this will raise an exception if no solution is found. The exception goes to stderr when CJam is run from the command line, and the correct result (0) is still printed to stdout. So this meets the consensus established at Should submissions be allowed to exit with an error?

The code may look longer than you would expect. The main reason is that CJam has no built-in for generating combinations. Or at least that's my excuse, and I'm sticking to it.


0       Push 0 result for exception case.
q~      Get and interpret input.
_,      Copy and get length of input value list.
2,      Push [0 1].
m*      Cartesian power. This generates all possible lists of 0/1 values with the
        same length as the input value list.
\       Swap input value list to top.
f.*     Apply element-wise product of input value list with all 0/1 lists.
        We now have all combinations of values, with 0 in place of unused values.
{       Start filter block.
  :+      Sum values.
  1$      Copy target sum to top.
  =       Compare.
},      Filter.
\;      Swap target sum to top and discard.
0f-     Remove 0 values. We now have all solution lists.
{,}$    Sort by length.
0=      Get first solution, which after sorting is the shortest.
        This will raise an exception if the list of solutions is empty, bailing
        out with the initial 0 on the stack.
,       Get length of solution.
+       Add the 0 we initially pushed for the exception case.

JavaScript (ES6), 84 bytes



Takes an Array of Numbers and a Number as arguments. Returns a number of Infinity if no result. It is a recursive function that subtracts from n and removes each element from the array one-by-one until n == 0.

f=(a,n,m=1e999,x)=> // m and x are not passed, they are here to declare them in the local
                    //     scope instead of globally, initialise m to Infinity
  n&&               // if n == 0, return 0
  a.map((v,i)=>     // iterate over each number in a
    (x=[...a],      // x = copy of a
    x.splice(i,1),  // remove the added number from the array
    x=f(x,n-v)+1)   // x = result for the numbers in this array
      <m?m=x:0      // set m to minimum result
  &&m               // return m


This test sets m to Infinity later instead of as a default argument to make it work in Chrome (instead of just Firefox).

var solution = f=(a,n,m,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0,m=1e999)&&m
Array (space-delimited) = <input type="text" id="array" value="143 1623 1646 16336 1624 983 122" /><br />
n = <input type="number" id="N" value="18102" /><br />
<button onclick="result.textContent=solution(array.value.split` `,N.value)">Go</button>
<pre id="result"></pre>


Haskell, 72 bytes

import Data.List
n#l=head$sort[length x|x<-subsequences l,sum x==n]++[0]

Returns 0 if there's no solution.

Usage example: 10 # [1,5,7,3,7,3,6,3,2,6,3] -> 2.

Find all sub-lists of the input list l which have a sum of n. Take the length of each such sub-list and sort. Append a 0 and take the first element.

If a singleton list is allowed for output, e.g. [2], we can save 7 bytes: n#l=minimum[length x|x<-subsequences l,sum x==n]. In case of no solution, the empty list [] is returned.


Vyxal, 9 bytes


Try it Online!

ṗ         # Powerset
 '   ;    # Filtered by
  ∑₀=     # Sublists that sum to input
      vL  # Get length of each
        g # Minimum

Jelly, 8 bytes


Try it online!

Outputs 0 if there's no solution

How it works

ŒPS=¥ƇẈṂ - Main link. Takes L on the left and n on the right
ŒP       - Powerset of L
    ¥Ƈ   - Keep those lists for which the following is true:
  S      -   The sum...
   =     -   ...equals n
      Ẉ  - Lengths of those kept
       Ṃ - Minimum

Python 3.9, 101 bytes

def f(l,t):
 for i in l:s|={k+i:min(s[k]+1,s.get(k+i,s[k]+1))for k in s}
 return s.get(t,-1)

Try it online!

Note : the |= operators was introduced in python 3.9 but TIO doesn't support that version.

Python 3, 105 bytes

def f(l,t):s={0:0};[s.update({k+i:min(s[k]+1,s.get(k+i,s[k]+1))for k in s})for i in l];return s.get(t,-1)

Try it online!

Ungolfed version:

def f(l,t):
  s={0:0}              # initialize the reached numbers
  for i in l:          # iterate through the list
    new_s = {}           # create a dict for the newly reached numbers
    for k in s:          # iterate through all the reached numbers
      new_s[k+i] = min(s[k]+1,s.get(k+i,s[k]+1)) # set the new number to the minimal number of steps
    s.update(new_s)      # update out dict with the new values
  return s.get(t,-1)   # returns the number of steps or -1 if the number is unreachable

Try it online!


there is probably some potential


Your Answer

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

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