Friends Pairing Problem

Problem Statement

Given n friends, each one can remain single or be paired up with another friend. Each friend can be paired only once. Find the total number of ways the friends can remain single or be paired.

Example:

• Input: n = 3
• Output: 4 (all single, or exactly one pair with one single)

Noob-Friendly Explanation

Imagine 3 friends — Alice, Bob, and Charlie — are going to a dance. Each person can either dance alone or pair up with one other person. Let's list all options:

1. All dance alone: (A), (B), (C)
2. A alone, B & C paired: (A), (B,C)
3. B alone, A & C paired: (B), (A,C)
4. C alone, A & B paired: (C), (A,B)

That's 4 ways! The pattern is: for the nth person, they either stay single (leaving n-1 to arrange) or pair with any of the n-1 others (leaving n-2 to arrange).

Approach 1: Brute Force (Recursion)

Intuition

For person n: either they stay single (solve for n-1) or they pair with one of n-1 others (solve for n-2). The recurrence is f(n) = f(n-1) + (n-1) × f(n-2).

Algorithm

1. Base cases: f(1) = 1, f(2) = 2
2. f(n) = f(n-1) + (n-1) × f(n-2)

public class Solution {
    public int friendsPairing(int n) {
        if (n <= 2) return n;

        // Stay single: f(n-1)
        // Pair with someone: (n-1) * f(n-2)
        return friendsPairing(n - 1) + (n - 1) * friendsPairing(n - 2);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Each call branches into two sub-calls
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Iterative DP)

Intuition

Use the same recurrence but compute it iteratively. We only need the two previous values at any point, so two variables suffice.

Algorithm

1. Initialize prev2 = 1 (f(1)) and prev1 = 2 (f(2))
2. For each i from 3 to n: current = prev1 + (i - 1) * prev2
3. Update prev2 and prev1
4. Return prev1

public class Solution {
    public int friendsPairing(int n) {
        if (n <= 2) return n;

        int prev2 = 1; // f(1)
        int prev1 = 2; // f(2)

        for (int i = 3; i <= n; i++) {
            int current = prev1 + (i - 1) * prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single loop from 3 to n
• Space Complexity: O(1) - Only two variables used