Given "n" friends, each one can remain single or can be paired up with some other friend.
Each friend can be paired only once.
Find out the total number of ways in which friends can remain single or can be paired up.
Input: n = 3
Output: 4
Explanation:
{1}, {2}, {3}
{1}, {2,3}
{1,2}, {3}
{1,3}, {2}
Input: n = 2
Output: 2
Explanation:
{1}, {2}
{1,2}
Solutions
Method 1: Memoization
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "n" changes, so we can store and reuse the result of a function(..n) call using a "n+1" array.
The array will store a particular state (n) if we get it the first time.
Now, if we come across the same state (n) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n).
In addition, O(n) auxiliary space was used by the table.
Method 2: Recursion
There are two options for the nth person:
1) The nth person remains single, so there is only one way for us to recur for the remaining n- 1 people, i.e 1*f(n-1) or f(n-1).
2) The nth person pairs up with any of the remaining n- 1 people. So, excluding the two people who form a pair for the remaining n-2 people, we get (n-1) * f(n-2) ways.
Therefore, we can recursively write f(n) as:
f(n) = f(n - 1) + (n - 1) * f(n - 2)
If there are 2 friends, there are 2 ways to arrange them ({1},{2} and {1,2}), and for a single friend, there is only 1 way to arrange them ({1}).
So, for n <= 2, return n.
Complexity
The time complexity of this solution is exponential O(2^n).
In addition, O(2^n) auxiliary space was used by the recursion stack.