# How Many Ways To Empty The Glove Box?

Inspired by this glove-themed 538 Riddler Express Puzzle.

You are given a positive integer n, and a list A = [a_1, a_2, ..., a_k] of k distinct positive integers.

Then a restricted composition is an ordered list P = [p_1, p_2, ..., p_m] where each p_i is a (not necessarily distinct) member of A, and p_1 + p_2 + ... + p_m = n.

So, if n = 10, and A = [2,3,4] then an example of a restricted composition would be P = [3,4,3]. Another example would be P = [2,3,3,2]. A third example would be P = [3,3,4]. But there's no restricted composition that starts [3,3,3,...], because 10-(3+3+3) = 1, which is not in A.

We want the total number of different restricted compositions given the inputs, as an integer.

## Inputs

A positive integer n and a list A of distinct positive integers. All reasonable input formats allowed.

## Output

The number of distinct restricted compositions.

## Terms and Conditions

This is ; and thus we seek the shortest submissions in bytes satisfying the constraints. Any use of the usual loopholes voids this contract.

## Test Cases

(5, [2, 3, 4]) => 2
(10, [2, 3, 4]) => 17
(15, [3, 5, 7]) => 8

• Ah, a variant on the knapsack problem. Related XKCD Apr 12 '20 at 6:17

# Python 2, 50 49 bytes

-1 byte thanks to @Jonathan Allan

f=lambda n,A:n>=0and(n<1)+sum(f(n-x,A)for x in A)


Try it online!

• A little bit of a switcharoo can save a byte Apr 12 '20 at 17:57

# JavaScript (ES6),  48  40 bytes

Takes input as (a)(n).

a=>g=n=>n>0?a.map(x=>t+=g(n-x),t=0)|t:!n


Try it online!

# J, 24 17 bytes

1#.[=1#.[:>@,{\@#


Try it online!

Recursive version was too verbose in J, so I went brute force.

Take the integers in the right arg as a boxed list and the target number n in the left arg.

• {\@# - We create a series of cartesian products of the list with itself, starting with 1 (the list unchanged) and up to n (the list crossed with itself n times).
• [:>@, We flatten all of those, open them, and sum them.
• [= Check which sums equal n. This returns a boolean list.
• 1#. Sum it.

# APL (Dyalog), 18 bytes

Accepts n as the right argument and A as the left argument.

{⍵>0:+/⍺∘∇¨⍵-⍺⋄⍵=0}


Try it online!

# Jelly,  6  5 bytes

ṗⱮẎ§ċ


Try it online! (Very inefficient.)

### How?

Builds all lists of lengths $$\1\$$ to $$\n\$$ made from the integers in $$\A\$$ and then counts how many sum to $$\n\$$.

ṗⱮẎ§ċ - Link: list of positive integers, A; positive integer, n
Ɱ    - map across x in (implicit range [1..n]) applying:
ṗ     -   Cartesian power -> all length x lists made from values in A
Ẏ   - tighten (to a list of lists)
§  - sum each list
ċ - count occurrences of (n)


{$[x>0;+/(x-y)o\:y;~x]}  Try it online! recursive # Io, 57 bytes Port of the Python answer. f :=method(n,A,if(n>0,A map(x,f(n-x,A))sum,if(n==0,1,0)))  Try it online! # Husk, 10 8 bytes #o=¹ΣuṖ*  Try it online! This is so ridiculously inefficient that it struggles on TIO to even run any of the given test cases: link is to a super-easy test case of n=2, a=[1,2,3] (for which output is 4). Repeats and concatenates (*) the input list n times, and then generates all possible subsets (uṖ - this is the slow step!). Then counts the number (#) of subsets for which the total equals n (o=¹Σ). # Wolfram Language (Mathematica), 56494643 41 bytes 2 bytes golfed thanks to J42161217 n_~f~a_=If[n<1,1+Sign@n,Tr[f[n-#,a]&/@a]]  Try it online! Initial solution: Length[Join@@Permutations/@IntegerPartitions[#,∞,#2]]&  Try it online! • nice port! 41 bytes Apr 11 '20 at 21:46 • @J42161217 Thanks! That's a clever use of infix notation btw, I wouldn't have thought of using it for function definition Apr 11 '20 at 22:01 • 39 bytes – att Nov 20 '20 at 1:23 # C (gcc), 89 bytes Port of the Python answer. Edit: Outgolfed by Noodle9 :/ int n;f(int x,int*a){if(x<=0)return!x;int y=0,i=0;while(i++<n)y+=f(x-a[i-1],a);return y;}  Try it online! • 72 bytes Apr 12 '20 at 23:47 # C (gcc), 65 63 bytes Saved 2 bytes thanks to my pronoun is monicareinstate!!! f(n,a,l,s,i)int*a;{for(s=i=!n;i<l&n>0;)s+=f(n-a[i++],a,l);n=s;}  Try it online! • You can remove i++ by moving the ++ to f(n-a[i],...). I do not know the algorithm nor the problem itself, but if I replace s=!n,i=0 with i=s=!n, I get the same answers for the test cases. Apr 12 '20 at 7:02 • @mypronounismonicareinstate Just moved the ++ but thanks for the i init! If !n isn't 0 the for loop isn't going to run and i isn't used. Nice one :-) Apr 12 '20 at 7:07 # Ruby, 40 36 bytes Python answer port but Ruby strict typing means I can't coerce booleans into integers. -4 bytes from dingledooper. f=->n,a{n>0?a.sum{|e|f[n-e,a]}:1<<n}  Try it online! • I think you can get around the 'boolean issue' by using 1<<n instead of n==0?1:0. Apr 12 '20 at 7:13 # Perl, 52 bytes $r.=1x$_."|"}{(1x$^I)=~/^($r@){1,$^I}$(?{$\++})(*F)/


## Usage

printf "2\n3\n4" | perl -p -i10 glovebox.pl


## Explanation

Attempts to turn the problem into a string matching one, then uses regex backtracking to do the hard work! In the example given above it ends up constructing a regex match similar to 1111111111 =~ /^(1{2}|1{3}|1{4}){1,10}$(?{$count++})(*F)/

This will cause the regex engine to attempt each combination of the regex, using (?{$count++}) to increase $count each time the engine matches the input and reaches that point in the pattern, but forcing a fail (*F) before the match returns to cause the engine to backtrack and start again with the next combination. $count ends up being the answer. Slightly different approach, was hoping it'd end up a bit shorter though... # Haskell, 37 bytes n!a|n<0=0|n<1=1|n>0=sum$(!a).(n-)<\$>a


Try it online!

Quick port of the Python answer, call as n ! a.

# Charcoal, 21 20 bytes

⊞υ¹Ｆθ⊞υ↨Φυ№η⁻⊕ιλ¹Ｉ⊟υ


Try it online! Link is to verbose version of code. Edit: Saved 1 byte by using base conversion from 1 instead of summing a potentially empty list. Explanation:

⊞υ¹


Start our result list with the number of solutions for n=0 which is always 1 (the empty list).

Ｆθ⊞υ


Loop n times, so that we calculate the results for 1..n, appending them to the result list.

↨Φυ№η⁻⊕ιλ¹


Sum those results so far that contribute to the next total. For example, if A is [2, 3, 4], then to calculate the result for n=10, we already know the results for n=0..9, but we only add the results for n=6, n=7 and n=8. The sum is calculated by converting from base 1 in case the list is empty.

Ｉ⊟υ


Print the result for n.

# 05AB1E, 11 7 bytes

L€ãO˜¹¢


-4 bytes thanks to @ovs.

Very slow approach!

Try it online or verify the first two test cases at once (third one times out..).

Explanation:

L        # Push a list in the range [1, first (implicit) input-integer]
€       # Map over each integer in this list
ã      #  Take the cartesian product of the second (implicit) input-list that many times
O     # Sum each inner-most list
˜    # Flatten the list of lists
¹¢  # And count how many times the first input occurs in this list
# (after which the result is output implicitly)


# 05AB1E, 12 bytes

ÅœʒåP}€œ€Ùg


Here a faster (but now way longer) approach using the Åœ builtin.

Explanation:

Åœ         # Get all lists of positive integer that sum to the (implicit) input-integer
ʒ        # Filter this list of lists by:
å       #  Check for each value whether it's in the second (implicit) input-list
P      #  And check if this is truthy for all of them
}€œ      # After the filter: get the permutations of each remaining list
€    # Flatten one level down
Ù   # Uniquify the list of lists
g  # Pop and push the length for the amount of remaining lists
# (after which the result is output implicitly)

• 7 bytes with your first approach: L€ãO˜¹¢
– ovs
Nov 19 '20 at 12:59
• @ovs Oh, that's indeed a lot better. Thanks! Nov 19 '20 at 13:21

# Julia 1.0, 35 bytes

f(n,A)=n>=0&&+(n<1,f.(n.-A,[A])...)


Try it online!

# R, 59 55 bytes

Edit: -4 bytes thanks to Giuseppe

g=function(t,l,u=t-l)sum(!u,unlist(sapply(u[u>0],g,l)))


Try it online!

Recursively removes each element from the glove box, and calls itself with the new total if there's anything left.

• Nov 19 '20 at 19:00
• @Giuseppe - Yes! Thanks! Nov 19 '20 at 20:00

# Wolfram Language (Mathematica), 54 bytes

Tr[Length/@Permutations/@IntegerPartitions[#,All,#2]]&


Try it online!

# Red, 81 80 bytes

f: func[x y][case[x = 0x < 0on[sum collect[foreach a y[keep f x - a y]]]]]


Try it online!

The same recursive approach almost everyone is using, much longer though.

# Racket, 74 64 bytes

(λ(x y)(if(< x 1)(+(sgn x)1)(apply +(map(λ(a)(f(- x a)y))y))))


Try it online!

# Wolfram Language (Mathematica), 36 bytes

Tr[Multinomial@@@FrobeniusSolve@##]&


Try it online!