CODEWITHSUNDEEP
arraysmathrecursion
Mahdi
Mahdi

Reputation: 41

Recursive function that returns the number of possible combinations

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

Example 2

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

Upvotes: 3

Views: 1882

Answers (2)

Rory Daulton
Rory Daulton

Reputation: 22544

You do not give a target language and you do not say just how much help you want. So I'll give the overall idea of an algorithm that should be simple to code if you know recursion in a certain language. Ask if you want more code in Python, my current preferred language.

You know you need to do recursion, and you have two things you could recurse on: the length of the given array or the length of the desired arrays. Let's recurse on the second, and let's say the given array is [0, 1, ..., n-1] since you know that the actual contents are irrelevant.

If the desired length r is 1 you know there are only n desired arrays, namely [0], [1], ..., [n-1]. So there is the base case for your recursion.

If you have a "combination" of length r-1, how can that be expanded to length r and keep the requirements? Look at the last element in the array of length r-1--let's call it k. The next element cannot be less than that, so all the possible arrays extended to length r are the r-1 array appended with k', 'k+1, ..., n-1. Those are n-k arrays of length r.

Is it clear how to code that? Note that you do not need to keep all the arrays of length r-1, you only need the count of how many arrays there are that end with the element 0 or 1 or ... n-1. That makes it convenient to code--not much memory is needed. In fact, things can be reduced further--I'll leave that to you.

Note that the interviewer probably did not want the code, he wanted your thought-process leading to the code to see the way you think. This is one way to think the problem through.

Upvotes: 2

meowgoesthedog
meowgoesthedog

Reputation: 15035

This algorithm can be expressed recursively because the solution can be expressed in terms of solutions for smaller inputs. "Smaller" here has two meanings:

  • A subset of the array; specifically the sub-array after the current element index

  • Solutions for smaller length; these can be added together to give the solution for length + 1

Stopping conditions:

  • When the array size A = 1 - only one combination can be generated

  • When the length L = 1 - number of combinations = number of elements in array

The fully recursive procedure is a surprisingly simple one-liner: 

return [recursive call to rest of array, same length] + 
       [recursive call to same array, length - 1]

This is called dynamic programming.

Code:

int F(int A, int L)
{
    if (A <= 1) return 1;
    if (L <= 1) return A;
    return F(A - 1, L) + F(A, L - 1);
}

Tests:

  • F(4, 2) = 10
  • F(2, 3) = 4
  • F(3, 5) = 21 (trace it with pen-and-paper to see for yourself)

EDIT: I've given an elegant and simple solution, but I perhaps haven't explained it as well as @RoryDaulton. Consider giving his answer credit too.

Upvotes: 4

Related Questions