305. Friends Pairing Problem

Given n friends, each of whom can either remain single or be paired up with exactly one other friend (a pairing is mutual and no one can be in more than one pair), count the total number of distinct ways to group them.

Input: A single line contains the integer n, the number of friends. Output: Print a single integer - the number of distinct ways to group them.

0 <= n <= 30

This is structurally similar to the recurrence for counting balanced binary trees or other 'combine smaller sub-cases' DP problems - recognizing the shared 'f(n) built from f(n-1) and f(n-2), weighted by a combinatorial factor' shape helps generalize across this whole family of counting problems.

Count the number of ways n friends can each either stay single or pair up with exactly one other friend. Brute force: Try every possible way of grouping n friends into singles and pairs directly - this involves combinatorially exploring which subsets pair up, when the direct recurrence computes the count without any explicit enumeration. Optimised: The recurrence directly captures the TWO mutually exclusive choices for the nth friend (stay single, or pair with any of n-1 others) - building this bottom-up in a 1D array computes f(n) in linear time, with the numbers growing fast enough that a wide integer type may be needed for larger n.

Use the exact same recurrence, but cache each computed f(k) the first time it's needed, in an array or map, and return the cached value immediately on any later request for the same k. Since there are only n distinct subproblems, memoizing guarantees each one is solved exactly once instead of being recomputed along every recursive path that reaches it. Time: O(n) Space: O(n)

Build the sequence from f(0) and f(1) upward iteratively; at each step only the previous two values are ever needed to compute the next one. Since no older values are ever referenced again, keep just the last two results in two variables instead of a full array, eliminating both recursion overhead and the memoization table. Time: O(n) Space: O(1)

Directly implement the recurrence f(n) = f(n-1) + (n-1) * f(n-2): the nth friend either stays single, leaving f(n-1) ways to group the rest, or pairs with any one of the other n-1 friends, leaving f(n-2) ways to group the remaining friends. Implemented as a plain recursive function with no caching, the same smaller subproblems like f(n-2) get recomputed repeatedly through different call paths, causing exponential blowup. Time: O(2^n) Space: O(n)

1. f(n) = f(n-1) + (n-1)*f(n-2), with f(0)=f(1)=1. 2. The nth friend either stays SINGLE (f(n-1) ways for the rest) or PAIRS with any ONE of the other n-1 friends (after which those remaining n-2 friends have f(n-2) ways among themselves). 3. This is the SAME recurrence as counting INVOLUTIONS (permutations that are their own inverse) on n elements.

Time: O(n) - building the sequence bottom-up from f(0) and f(1). Space: O(1) if only the previous two values are kept, or O(n) if the full sequence is stored.

Test n = 0 (1 way, the empty grouping) and n = 30 (upper bound), where the count grows fast enough to need a wide integer type, per the problem's own hint.

Be ready to mention the mathematical connection to 'involutions' (self-inverse permutations) - this problem is a direct real-world framing of that exact combinatorial concept, useful context if it's phrased differently elsewhere.