Generate Parentheses | Leetcode 22 | Backtracking Approach

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

Here’s the [Problem Link] to begin with.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Solution: Backtracking Approach

Intuition

Think of this like building a balanced structure with opening and closing brackets! For n pairs of parentheses, you need exactly n opening ‘(‘ and n closing ‘)’ brackets. But here’s the catch – at any point, you can’t have more closing brackets than opening ones (that would be invalid like “)(” ). It’s like building with blocks where you need a foundation (opening bracket) before you can close it. We use backtracking to try placing ‘(‘ or ‘)’ at each position, keeping track of how many “unmatched” opening brackets we have. When we complete all positions and have zero unmatched brackets, we found a valid combination!

Detailed Approach

1. Initialize Setup: Create an array of empty strings with length 2*n (since we need n pairs).
2. Recursive Function: Use a helper function that takes current index, running total of unmatched opening brackets, the brackets array, and result list.
3. Base Case: When index reaches 2*n, check if total equals 0 (all brackets matched) – if yes, add to results.
4. Pruning Conditions:
   • If total > n: too many unmatched opening brackets, stop this path.
   • If total < 0: more closing than opening brackets, invalid, stop this path.
5. Try Opening Bracket: Place ‘(‘ at current position, increment total (one more unmatched opening), and recurse.
6. Try Closing Bracket: Place ‘)’ at current position, decrement total (match one opening bracket), and recurse.
7. Backtrack: The array gets overwritten naturally as we try different choices.

Code

class Solution:
    def solve(self, index, total, brackets, result):
        # Base case: If we've filled all positions
        if index >= len(brackets):
            if total == 0:  # All brackets are properly matched
                result.append("".join(brackets))  # Add valid combination
            return
        
        # Pruning: Too many unmatched opening brackets
        if total > len(brackets) // 2:
            return
        
        # Pruning: More closing brackets than opening (invalid)
        if total < 0:
            return
        
        # Choice 1: Place opening bracket '('
        brackets[index] = "("
        Sum = total + 1  # Increment unmatched opening count
        self.solve(index + 1, Sum, brackets, result)
        
        # Choice 2: Place closing bracket ')'
        brackets[index] = ")"
        Sum = total - 1  # Decrement unmatched opening count
        self.solve(index + 1, Sum, brackets, result)

    def generateParenthesis(self, n: int) -> List[str]:
        brackets = [""] * (n * 2)  # Array of size 2n for n pairs
        result = []                # List to store all valid combinations
        self.solve(0, 0, brackets, result)  # Start with index 0, total 0
        return result

Code Explanation

The solve function uses backtracking to build parentheses combinations while maintaining validity through the total parameter. The total keeps track of how many opening brackets are currently “unmatched” (waiting for their closing pair). At each position, we try placing ‘(‘ (increases unmatched count) and ‘)’ (decreases unmatched count). The key insight is the pruning: if total goes negative, we have more closing than opening brackets (invalid), and if total exceeds n, we have too many unmatched opening brackets. When we fill all positions and total equals 0, all brackets are properly matched, so we add it to results.

Dry Run

Let’s trace through n=2 (need 4 positions total):

Start: index=0, total=0, brackets=[“”,””,””,””]

Try ‘(‘ at index 0:

• brackets=[“(“,””,””,””], total=1, index=1Try ‘(‘ at index 1:
  • brackets=[“(“,”(“,””,””], total=2, index=2Try ‘(‘ at index 2:
    • total=3 > 2 (n), prune this path
    Try ‘)’ at index 2:
    • brackets=[“(“,”(“,”)”,””], total=1, index=3Try ‘(‘ at index 3:
      • total=2, index=4 → total≠0, don’t add
      Try ‘)’ at index 3:
      • brackets=[“(“,”(“,”)”,”)”], total=0, index=4 → add “(())” to result
  Try ‘)’ at index 1:
  • brackets=[“(“,”)”,””,””], total=0, index=2Try ‘(‘ at index 2:
    • brackets=[“(“,”)”,”(“,””], total=1, index=3Try ‘)’ at index 3:
      • brackets=[“(“,”)”,”(“,”)”], total=0, index=4 → add “()()” to result

Try ‘)’ at index 0:

• total=-1 < 0, prune this path immediately

Result: ["(())", "()()"]

Time and Space Complexity

• Time Complexity: O(4^n / √n) – This is the nth Catalan number, which represents the number of valid parentheses combinations. The backtracking explores this many valid paths plus some pruned invalid ones.
• Space Complexity: O(n) – The recursion stack depth is 2n, plus space for the brackets array.

Simplifying It

This backtracking approach is like carefully building a tower with opening and closing pieces. The total acts like a balance meter, it goes up when you add an opening piece (creating an imbalance that needs fixing) and goes down when you add a closing piece (fixing the imbalance). You can only close what you’ve opened, and at the end, everything must be perfectly balanced (total = 0). The pruning conditions act like safety checks, preventing you from building impossible structures. It’s a beautiful example of how backtracking can generate all valid solutions while efficiently avoiding invalid paths!

This problem is fantastic for understanding constraint-based generation and is a common interview question that tests your ability to think about valid states and pruning conditions.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.