Minimum number of numbers to sum to exactly n

Question

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

Introduction

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.

Challenge

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.

Input

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

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:

2

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

Input:

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

Output:

2
3
-1

Scoring

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

The top answer will be accepted on Christmas.

Answer 1

Pyth, 12 11 bytes

lhafqsTQyEY

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.

Answer 2

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!

Answer 3

Mathematica, 73 65 bytes

Min[Length/@Select[IntegerPartitions[#2,#2,#],Sort@#==Union@#&]]&

Pure function, returns ∞ if there is no solution.

Answer 4

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

Answer 5

Mathematica, 45 bytes

Min@Cases[Subsets@#,i_/;Tr@i==12:>Length@#2]&

Answer 6

CJam, 34 bytes

0q~_,2,m*\f.*{:+1$=},\;0f-{,}$0=,+

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.

Explanation:

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.

Answer 7

JavaScript (ES6), 84 bytes

f=(a,n,m=1e999,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0)&&m

Explanation

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

Test

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>

Answer 8

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.