Friends Pairing Problem (Solution)

Problem Statement

Given a total of n friends, each friend can either remain single or can be paired up with some other friend. The pairing for each friend can be done only once. Find out the total number of ways in which the friends can be single or get paired up.

Sample Test Cases

Input 1: n = 2
Output 1: 2
Explanation 1: There are only 2 ways for the pairings to be made, both friends get paired into 1 group or both friends remain single.

Input 2: n = 3
Output 2: 4
Explanation 2: The pairings are listed below:
{1}, {2}, {3}
{1, 2}, {3}
{1, 3}, {2}
{2, 3}, {1}

Recursive Brute Force Method

The problem can be solved with recursion by considering the choices we have for the nth person. For the nth person,

• The nth person stays single or unpaired, and we recurse for the remaining n – 1 people.
• Nth person pairs up with any for the remaining n – 1 people. The number of ways of doing this (n – 1) * Rec(n – 2).

The recurrence can then be written as:

• Rec(n) = Rec(n – 1) + (n – 1) * Rec(n – 2)

Which can be easily simulated with brute force.

Base Case: Note that if there are 2 friends, there are 2 ways to arrange them, and for a single friend, there is only 1 way to arrange them. So for n <= 2, the answer will be n.

C++ Code

int countPairings(int n) {
    return n <= 2 ? n : countPairings(n - 1) + (n - 1) * countPairings(n - 2);
}

Java Code

public static int countPairings(int n) {
        return n <= 2 ? n : countPairings(n - 1) + (n - 1) * countPairings(n - 2);
    }

Python Code

def countPairings(n):
    return n if n <= 2 else countPairings(n - 1) + (n - 1) *
countPairings(n - 2)

Time Complexity: Exponential
Space Complexity: O(1) // If recursion stack space is ignored.

Approach 2: Memoization

Observe from the above recursion tree, that there are many subproblems in the brute force method which are being called again and again. We can memoize these subproblems so as to avoid them from being recalculated again and again with a dynamic programming approach.

Here, the states of our dp will be dp[n]: Number of ways to arrange a total of n friends. The transitions will be the same as in the brute force approach.

C++ Implementation

int countPairings(int n, vector < int > & dp) {
  if (dp[n] != -1) {
    return dp[n];
  }
  dp[n] = n <= 2 ? n : countPairings(n - 1, dp) + (n - 1) * countPairings(n - 2, dp);
  return dp[n];
}

Java Implementation

public static int countPairings(int n, int[] dp) {
  if (dp[n] != -1) {
    return dp[n];
  }
  dp[n] = n <= 2 ? n : countPairings(n - 1, dp) + (n - 1) * countPairings(n - 2, dp);
  return dp[n];
}

Python Implementation

def countPairings(n, dp):
    if dp[n] != -1:
        return dp[n]
    dp[n] = n if n <= 2 else countPairings(n - 1, dp) + (n - 1) * countPairings(n - 2, dp)
    return dp[n]

Time Complexity: O(n)
Space Complexity: O(n)

Approach 3: Iterative Dynamic Programming

Similar to the recursive memoization-based dynamic programming approach, we can also solve the problem with an iterative dynamic programming-based approach, i.e with tabulation. The states and the transitions for this approach will be the same as the ones for the recursive approach just implemented in an iterative manner.

C++ Implementation

int countPairings(int n) {
  vector < int > dp(n + 1);
  for (int i = 0; i <= n; i++) {
    if (i <= 2) {
      dp[i] = i;
    } else {
      dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
  }
  return dp[n];
}

Java Implementation

public static int countPairings(int n) {
  int dp[] = new int[n + 1];
  for (int i = 0; i <= n; i++) {
    if (i <= 2) {
      dp[i] = i;
    } else {
      dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
  }
  return dp[n];
}

Python Implementation

def countPairings(n):
    dp = [0] * (n + 1)
    for i in range(n + 1):
        if i <= 2:
            dp[i] = i
        else:
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]
    return dp[n]

Time Complexity: O(n)
Space Complexity: O(n)

Approach 4: Combinatorics Based Approach

The problem given is basically equivalent to the combinatorial problem of “In how many ways can we divide a total of n items into multiple groups (maximum group size here being 2).” This problem is solved by the following formula:

Referring to the above formula, we can precompute the factorials in our problem, and using them calculate the result from the given formula.

C++ Code

int countPairings(int n) {
  vector < int > fact(n + 1);
  fact[0] = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = fact[i - 1] * i;
  }
  int groupsOfOnes = n, groupsOfTwos = 1, ans = 0;
  while (groupsOfOnes >= 0) {
    ans += fact[n] / (groupsOfTwos * fact[groupsOfOnes] * fact[(n - groupsOfOnes) / 2]);
    groupsOfOnes -= 2;
    groupsOfTwos <<= 1;
  }
  return ans;
}

Java Code

public static int countPairings(int n) {
  int fact[] = new int[n + 1];
  fact[0] = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = fact[i - 1] * i;
  }
  int groupsOfOnes = n, groupsOfTwos = 1, ans = 0;
  while (groupsOfOnes >= 0) {
    ans += fact[n] / (groupsOfTwos * fact[groupsOfOnes] * fact[(n - groupsOfOnes) / 2]);
    groupsOfOnes -= 2;
    groupsOfTwos <<= 1;
  }
  return ans;
}

Python Code

def countPairings(n):
    fac = [1] * (n + 1)
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i
    groupsOfOnes = n
    groupsOfTwos = 1
    ans = 0
    while groupsOfOnes >= 0:
        ans += fac[n] // (
            fac[groupsOfOnes] * fac[(n - groupsOfOnes) // 2] * groupsOfTwos
        )
        groupsOfOnes -= 2
        groupsOfTwos <<= 1
    return ans

Time Complexity: O(n)
Space Complexity: O(n)

FAQs

Q. How does the brute force approach have exponential time complexity?
A. From the recursion tree, we can observe that the tree divides into two branches at each level. So the number of states to be visited becomes exponential in number when measured as a function of input n.

Q. How many states does the recursion depend upon in this problem?
A. The recursion is solely dependent on the number of people (n) as the state for this problem.