Author: TSEC CodeCell
Find the number of ways a group can be split into a combination or pairs and solo units mod 10^9 +7.
We must find ways N distinct people can form pairs out of which some can remain alone.
So the Nth person can stay alone (1 way to do that), or pair with someone from 1 to N-1.
Thus f(N)= 1* f(N-1) + N-1 * f(N-2)
The solution can be optimized by caching all the results in an array.
The precomputation of all results take O(N) time and O(1) for answering each test query.
Author’s solution can be found here.