Inspired by this glove-themed 538 Riddler Express Puzzle.
Task
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 code-golf; 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