I came up with 5 different solutions for this:
- Simple recursive O(n!)
- Recursive with dynamic programming memoization O(nm)
- Iterative with dynamic programming O(nm)
- Mathematical using binomial coefficient O(max(n,m))
- Mathematical using binomial coefficient optimised
Source code for the different solutions:
Recursive
Recursive with dynamic programming
Iterative with dynamic programming
Mathematical using binomial coefficient
Mathematical using binomial coefficient optimised