I had an interview and was asked a question that I'd like to understand the solution.
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
One "hint" was offered. The interviewer said the array itself shouldn't matter; the length was all that was needed.
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) = 10F(2, 3) = 4F(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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments