NUHMAN.com

Introduction

LeetCode 22: Generate Parentheses is a popular recursion and backtracking problem where the goal is to generate all combinations of well-formed parentheses for a given number of pairs.

This problem tests your ability to explore a state space tree and prune invalid configurations, which is crucial for more complex backtracking challenges.

Problem Statement

Given n pairs of parentheses, write a function that returns all combinations of well-formed parentheses.

Examples

go

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

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

Approach: Backtracking

This problem is best solved using backtracking, which explores all possible valid combinations by:

• Adding an opening bracket ( if we still have left parentheses available.
• Adding a closing bracket ) only if it does not exceed the number of opening brackets used so far.

Key Rules:

• Never allow more ) than ( at any point.
• Stop recursion when both open and close counts equal n.

Go Implementation

go

package main

import (
    "fmt"
)

func generateParenthesis(n int) []string {
    var result []string

    var backtrack func(curr string, open, close int)
    backtrack = func(curr string, open, close int) {
        if len(curr) == 2*n {
            result = append(result, curr)
            return
        }

        if open < n {
            backtrack(curr+"(", open+1, close)
        }

        if close < open {
            backtrack(curr+")", open, close+1)
        }
    }

    backtrack("", 0, 0)
    return result
}

func main() {
    n := 3
    result := generateParenthesis(n)
    fmt.Printf("All valid parentheses for n = %d:\n", n)
    for _, comb := range result {
        fmt.Println(comb)
    }
}

Step-by-Step Example (n = 2)

State tree:

arduino

""
├── "("
│   ├── "(("
│   │   └── "(())"
│   └── "()"
│       └── "()()"

Result:

css

["(())", "()()"]

Time and Space Complexity

• Time Complexity: O(2^n), more precisely O(4^n / √n) due to the Catalan number.
• Space Complexity: O(2n) for recursion stack + O(number of results)

Key Takeaways

• This is a classic backtracking problem with constraints.
• Think of the parentheses as a tree: at each level, you decide whether to add ( or ).
• The condition close < open prevents invalid strings like ())(.