Introduction

The Generate Parentheses problem is one of the most important and frequently asked backtracking questions in coding interviews.

At first glance, it may look like a simple string generation problem—but the real challenge is to generate only valid (well-formed) parentheses combinations.

This problem is a perfect example of:

1. Constraint-based recursion
2. Backtracking with conditions
3. Decision tree pruning

In this article, we’ll break down the intuition, understand the constraints, and implement a clean and efficient solution.

🔗 Problem Link

LeetCode: Generate Parentheses

Problem Statement

Given n pairs of parentheses:

👉 Generate all combinations of well-formed parentheses

Examples

Example 1

Input:

n = 3

Output:

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

Example 2

Input:

n = 1

Output:

["()"]

Key Insight

We are not generating all possible strings—we are generating only valid parentheses.

Rules of Valid Parentheses

1. Number of ( must equal number of )
2. At any point:

Intuition (Decision Making)

At every step, we have two choices:

But we cannot always take both choices.

Valid Conditions

When can we add "("?

When can we add ")"?

👉 This ensures the string always remains valid.

Decision Tree (n = 3)

👉 You can add your tree diagram here for better visualization.

Conceptual Flow

Invalid paths like ")(" are never explored because of constraints.

Approach: Backtracking with Constraints

Idea

1. Keep track of:
2. Remaining open brackets
3. Remaining close brackets
4. Build string step by step
5. Only take valid decisions

Java Code

Step-by-Step Execution (n = 2)

Complexity Analysis

1. Time Complexity: O(4ⁿ / √n) (Catalan Number)
2. Space Complexity: O(n) recursion stack

Why Catalan Number?

The number of valid parentheses combinations is:

Why This Approach Works

1. It avoids invalid combinations early
2. Uses constraints to prune recursion tree
3. Generates only valid results
4. Efficient compared to brute force

❌ Naive Approach (Why It Fails)

Generate all combinations of ( and ):

1. Total combinations = 2^(2n)
2. Then filter valid ones

👉 Very inefficient → TLE

Key Takeaways

1. This is a constraint-based recursion problem
2. Always:
3. Add "(" if available
4. Add ")" only if valid
5. Backtracking avoids invalid paths
6. Important pattern for interviews

Common Interview Variations

1. Valid parentheses checking
2. Longest valid parentheses
3. Remove invalid parentheses
4. Balanced expressions

Conclusion

The Generate Parentheses problem is a must-know backtracking problem. It teaches how to apply constraints during recursion to efficiently generate valid combinations.

Once mastered, this pattern becomes extremely useful in solving many advanced recursion problems.

Frequently Asked Questions (FAQs)

1. Why can’t we add ")" anytime?

Because it may create invalid sequences like ")(".

2. What is the key trick?

Ensure:

3. Is recursion the best approach?

Yes, it is the most intuitive and efficient method.