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.
Examples :
Input : n = 3
Output : 4
Explanation
{1}, {2}, {3} : all single
{1}, {2, 3} : 2 and 3 paired but 1 is single.
{1, 2}, {3} : 1 and 2 are paired but 3 is single.
{1, 3}, {2} : 1 and 3 are paired but 2 is single.
Note that {1, 2} and {2, 1} are considered same.
f(n) = ways n people can remain single
or pair up.
For n-th person there are two choices:
1) n-th person remains single, we recur
for f(n - 1)
2) n-th person pairs up with any of the
remaining n - 1 persons. We get (n - 1) * f(n - 2)
Therefore we can recursively write f(n) as:
f(n) = f(n - 1) + (n - 1) * f(n - 2)
class Solution {
// O(n) -> space solution
public int countFriendsPairings(int n) {
if (n == 0)
return 1;
// Recursive formula -> 2 case :
// 1) n stays single -> fn(n-1)
// 2) n pairs with anyone from 1->n-1 => (n-1)*fn(n-2)
// Fn(n-2) shows the ans from remaining n-2 people
// dp[i] -> Number of ways i people can stay paired up or single
int dp[] = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
}
return dp[n];
}
// O(1) space solution
public int countFriendsPairings(int n) {
if (n == 0 || n == 1)
return 1;
int dp0 = 1, dp1 = 1;
for (int i = 2; i <= n; i++) {
int dpi = dp1 + (i - 1) * dp1;
dp0 = dp1;
dp1 = dpi;
}
return dp1;
}
}