Handshakes That Don't Cross - Solution & Explanation

Problem Overview: Given an even number n representing people standing in a circle, each person must shake hands with exactly one other person. Handshakes cannot cross. The task is to count how many valid pairing arrangements exist.

Approach 1: Brute Force Recursive Pairing (Exponential)

The most direct idea tries every possible handshake choice for the first person. Pair person 0 with any other valid partner 2k+1, which splits the circle into two independent subproblems. Recursively count valid pairings inside the left and right partitions and multiply them. This naturally models the non‑crossing constraint because once a pair is chosen, everything inside and outside that arc must remain independent. The recursion recomputes the same states many times, leading to exponential time complexity O(2^n) with recursion depth O(n).

Approach 2: Memoization Search (Catalan DP) (Time: O(n^2), Space: O(n))

The recursive structure reveals a classic Catalan number recurrence. Let dp[i] represent the number of valid ways to form non‑crossing handshakes among 2 * i people. If the first person pairs with person 2k+1, the people inside that arc form k pairs and the outside group forms i-1-k pairs. The recurrence becomes dp[i] = sum(dp[k] * dp[i-1-k]). A top‑down dynamic programming solution with memoization caches each dp[i], eliminating repeated computation. Since each state iterates over at most i splits, the total runtime becomes O(n^2) and space O(n). Results are typically computed modulo 1e9+7.

Approach 3: Bottom-Up Dynamic Programming (Time: O(n^2), Space: O(n))

The same recurrence can be implemented iteratively. Initialize dp[0] = 1, then compute values for increasing numbers of pairs. For each i, iterate k from 0 to i-1 and accumulate dp[k] * dp[i-1-k]. This avoids recursion overhead and keeps the logic straightforward. The approach still performs roughly n^2/2 multiplications but is easy to reason about and commonly used when solving Catalan problems in math and dynamic programming.

Approach 4: Catalan Number Formula (Time: O(n), Space: O(n))

The sequence of valid handshake counts is exactly the Catalan sequence. For i pairs, the value equals C_i = (2i)! / ((i+1)! * i!). With precomputed factorials and modular inverses, the result can be calculated in linear time. This approach is mathematically elegant and faster asymptotically, but interviewers usually expect candidates to derive the DP recurrence before jumping to the closed form.

Recommended for interviews: Use the memoized or bottom‑up Catalan DP. It clearly shows you understand the non‑crossing partition insight and the recurrence structure. Mentioning the Catalan number connection strengthens the explanation and demonstrates deeper algorithmic knowledge.