Generate Parentheses

Difficulty: Medium

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Explanation: All 5 valid combinations of 3 pairs of parentheses.

Brute-force approach

This is a recursion-focused problem. We go directly to the recursive solution using the Leap of Faith approach.

Time complexity: - · Space complexity: -

Optimal approach

Key insight: At each position, you make a choice ('(' or ')'), trust recursion to handle everything after that choice, and the two rules (open < n, close < open) guarantee every completed string is valid.

Use the Leap of Faith recipe: at each position, place '(' or ')' if allowed, and trust recursion to generate all valid continuations from there.

Steps

  1. Initialize empty result list
  2. Call backtrack('', 0, 0)
  3. Base case: if string length == 2n, add to result
  4. If open < n, Leap of Faith: backtrack(current + '(', open + 1, close)
  5. If close < open, Leap of Faith: backtrack(current + ')', open, close + 1)
  6. Return result

Time complexity: O(4^n / √n) · Space complexity: O(n)