I had an interview and was asked a question that I'd like to understand the solution.

The Question

Create a recursive function that returns the number of possible combinations of arrays of a given length that could be made from an array of non-repeating consecutive integers.

f(array, length) = Combinations

Example 1

• array = [0,1,2,3]
• length = 2
• Combinations = 10 (all combinations: [0,0] [0,1] [0,2] [0,3] [1,1] [1,2] [1,3] [2,2] [2,3] [3,3])
• Note that [0,0] is allowed but [1,0] is not because [0,1] is defined

Example 2

• array = [0,1]
• length = 3
• Combinations = 4 (all combinations: [0,0,0] [0,0,1] [0,1,1] [1,1,1])

One "hint" was offered. The interviewer said the array itself shouldn't matter; the length was all that was needed.