# 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 – Value Ink Apr 12 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!

# 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!

# K (ngn/k), 23 bytes

{$[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! # 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)  # 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 – J42161217 Apr 11 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 – DanTheMan Apr 11 at 22:01 # Charcoal, 21 bytes ⊞υ¹Ｆθ⊞υΣＥυ∧№η⁻⊕ιλκＩ⊟υ  Try it online! Link is to verbose version of code. 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 zeroing out the unwanted results to avoid edge cases in Charcoal. Ｉ⊟υ  Print the result for n. # 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. – my pronoun is monicareinstate Apr 12 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 :-) – Noodle9 Apr 12 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. – dingledooper Apr 12 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.

# Wolfram Language (Mathematica), 54 bytes

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


Try it online!

# C (gcc), 89 bytes

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!

# Red, 81 80 bytes

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


Try it online!

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

# 05AB1E, 11 bytes

¯sƒINã«}O¹¢


Very slow approach!

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

Explanation:

¯        # Push an empty list []
sƒ      # Loop N in the range [1, first input-integer]:
I     #  Push the second input-list
Nã   #  Take the cartesian product of this list N times
«  #  Merge it to the earlier list
}O     # After the loop: sum all inner 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


A faster approach using the Åœ builtin, but unfortunately 1 byte longer.

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)


# Racket, 74 64 bytes

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


Try it online!