Friends pairing problem in Python

Key takeaways:

  • The problem illustrates a group of N friends who can either be paired with each other or left single. However, each friend can only be paired once. We need to determine the total number of ways this N group of friends can be paired or left completely single.

  • The solution uses dynamic programming with the recurrence relation f(n)=f(n−1)+(n−1)×f(n−2)f(n)=f(n−1)+(n−1)×f(n−2) to efficiently calculate arrangements by considering each friend's options.

  • The solution has a time complexity of O(n)O(n) and a space complexity of O(n)O(n).

In social dynamics, the ways friends can interact and form groups have always intrigued us. Imagine a group of N friends who can either pair up or remain single. The challenge lies in determining all the possible combinations in which these friends can either form pairs or stay single, adhering to the rule that each friend can only be paired once. This problem finds the combinatorial possibilities of social interactions and relationships. Understanding this problem not only provides insights into combinatorial mathematics but also finds applications in network theory, graph theory, and even in organizing social events. Solving this LeetCode discuss problem will enhance our skills and allow us to tackle similar problems more efficiently.

Problem statement

Consider a group of N friends who can either be paired with each other or left single. However, each friend can only be paired once. We need to determine the total number of ways this N group of friends can be paired or left completely single.

The illustrations below demonstrate a way this problem can be solved:

We need to make all combinations of the friends.
We need to make all combinations of the friends.
1 of 5

Constraints:

  • Each friend can only be paired once or not at all.

  • Pairs { A, B } and { B, A } are considered the same.

  • 1 ≤\leq N ≤\leq 10410^4

Knowledge test

Let’s test your understanding of the problem.

1

How many ways can you arrange 2 friends?

A)

1

B)

2

C)

3

D)

4

Question 1 of 30 attempted

Algorithm

Suppose we have a group of three friends: A, B, and C. We want to determine the total ways these friends can be paired. There are two possibilities:

  • Firstly, all friends remain single, and none gets coupled with the other.

  • The second would be to form a pair of two friends while leaving one friend out. If we count the pairs formed from a group of three friends, there would be three.

We can solve this problem using a dynamic programming approach. If we carefully analyze the scenario, we can see it is a combination problem. The goal is to divide a group of N friends into the maximum number of pairs. The function f(n) represents the number of ways to arrange n friends where each friend can either remain single or be coupled.

For the nth friend, there are two possibilities:

  • The nth friend remains single. In this case, we calculate the total pairs that can be formed with the remaining n - 1 friends. This is represented by f(n - 1).

  • The nth friend pairs with one of the remaining n - 1 friends. There are n - 1 choices for this pair. After pairing, we calculate the total pairs for the remaining n - 2 friends. This is represented by (n - 1) * f(n - 2).

Thus, the total number of ways to arrange n friends is given by the formula:

We can implement this problem using the recursive brute force method or memoization. If we observe the recursion tree below, we’ll notice that many subproblems can be stored in memory instead of recalculating them repeatedly, preventing the constant back-and-forth of having to calculate each subproblem every time.

Recursion tree
Recursion tree

Now, let’s look at the step-by-step algorithm for this problem:

  1. Initialize: Start by setting up a list or array memory to store results.

  2. Base cases: Initialize memory[0] = 0, memory[1] = 1, and memory[2] = 2 to cover cases with 0, 1, and 2 friends.

  3. Iterate: Loop through each number of friends from 3 up to total_friends.

  4. Calculate: For each i > 2, compute memory[i] using a formula that combines previously computed values in memory.

  5. Result: After completing the loop, memory[total_friends] will hold the total number of ways to arrange total_friends friends into couples.

Coding example

Now, let’s run the Python code below and implement the iterative dynamic programming approach. 

def make_friend_couples(total_friends):
    # Empty list that will be populate with zeros
    memory = []
    for i in range(0,total_friends+1):
      memory.append(0)
    for i in range(total_friends+1):
      if i<=2:
        # total couples = total friends when i<=2
        memory[i] = i 
      elif i>2:
        # total couples determined by the formula discussed above
        memory[i] = memory[i-1] + (memory[i-2] * (i-1)) 
    total_couples = memory[total_friends]
    return total_couples
    
print(make_friend_couples(6)) # expected output = 76
print(make_friend_couples(3)) # expected output = 4
print(make_friend_couples(5)) # expected output = 26
print(make_friend_couples(2)) # expected output = 2
print(make_friend_couples(8)) # expected output = 764
Friends Pairing Problem in Python

Time complexity

The time complexity for this iterative approach is O(n){O(n)} because we iterate over each friend in the group exactly once.

Space complexity

The space complexity for this solution is O(n){O(n)} because as the size of our friend circle increases, so does the size of the memoization list.

Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
YouTubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved