Recursion & BacktrackingMediumO(4^n / sqrt(n)) time · O(n) space

Generate Parentheses

Mahabharata — Vyasa's Verses — All Valid Ways to Arrange n Pairs of Brackets

n जोड़ी कोष्ठक — सभी वैध क्रम। खुला जोड़ो जब space हो — बंद जोड़ो जब खुला हो॥

*n pairs of parentheses — all valid arrangements. Add open when space remains — add close when open exists.*

The Story

Generate all valid combinations of n pairs of parentheses.

For n=3: ["((()))","(()())","(())()","()(())","()()()"].

**Backtracking:** At each step, we can: 1. Add '(' if `open < n` (still have opening brackets to use) 2. Add ')' if `close < open` (can only close if there's an open bracket)

Base case: when string length = 2n, add to result.

```java void backtrack(List<String> res, String s, int open, int close, int n) { if (s.length() == 2*n) { res.add(s); return; } if (open < n) backtrack(res, s+"(", open+1, close, n); if (close < open) backtrack(res, s+")", open, close+1, n); } // Call: backtrack(res, "", 0, 0, n) ```

Trace n=2: - ("", 0, 0): add '(' → ("(", 1, 0) - add '(' → ("((", 2, 0) - add ')' → ("(()", 2, 1) - add ')' → ("(())", 2, 2) → add to result - add ')' → ("()", 1, 1) - add '(' → ("()(", 2, 1) - add ')' → ("()()", 2, 2) → add to result

Result: ["(())", "()()"] ✓ (Both valid for n=2)

**The key insight:** At any position: - `open` counts how many '(' placed so far - `close` counts how many ')' placed so far - Valid if close ≤ open ≤ n at all times

We never need to backtrack explicitly (undo a character) because we pass the string by value — each branch gets its own copy.

The Generate-and-Filter Approach

Generate all 2^(2n) binary strings of (, ), filter valid ones. O(n×2^(2n)).

java

// Generate all possibilities and filter
void generateAll(List<String> valid, String s, int n) {
    if (s.length() == 2*n) {
        if (isValid(s)) valid.add(s);
        return;
    }
    generateAll(valid, s+"(", n);
    generateAll(valid, s+")", n);
}

The Two-Condition Backtracking Wisdom

Backtrack with open/close counts. Add '(' if open<n. Add ')' if close<open. Base: length==2n. Never needs explicit undo (string passed by value).

java

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(res, "", 0, 0, n);
    return res;
}

void backtrack(List<String> res, String s, int open, int close, int n) {
    if (s.length() == 2 * n) { res.add(s); return; }
    if (open < n) backtrack(res, s + "(", open + 1, close, n);
    if (close < open) backtrack(res, s + ")", open, close + 1, n);
}

Step-by-Step Walkthrough

n=1
"": open<1 → "("(1,0)
  "(": close<open(0<1) → "()"(1,1)
    "()": len=2==2×1 → add
Result: ["()"] ✅

Deep Insight

**Why no explicit backtrack?** String concatenation `s + "("` creates a new string — the original s is unchanged. Each branch of the tree works with its own copy. Compare with list-based backtracking (like rb-8 Permutations) where we explicitly add to a list and then remove after recursion.

**Count of valid parentheses = Catalan number C(n) = C(2n,n)/(n+1).** For n=4: 14. The time complexity reflects this growth: O(4^n / sqrt(n)) is the nth Catalan number.

**The condition `close < open`** ensures we never have more closing than opening brackets at any prefix, which is the definition of valid parentheses.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n × 4^n)	O(n)	Generate all 4^n strings, validate each
Optimal	O(4^n / sqrt(n))	O(n)	Catalan number of valid combinations × n each

Pattern Recognition

✅ Generate valid parentheses → count-based backtracking
✅ open<n: can add '('
✅ close<open: can add ')'
✅ No explicit undo (string passed by value)

**LeetCode Trigger Phrases:**
→ "generate parentheses"
→ Generate all valid bracket arrangements
→ Two-condition backtracking

Bhagavad Gita 4.24

ब्रह्मार्पणं ब्रह्म हविर्ब्रह्माग्नौ ब्रह्मणा हुतम्। ब्रह्मैव तेन गन्तव्यं ब्रह्मकर्मसमाधिना॥

The act of offering is Brahman; the oblation is Brahman; offered by Brahman into the fire of Brahman. Brahman is to be attained by one who meditates on Brahman in every action.

Connection: Valid parentheses form complete, balanced pairs — every opening matched by a closing, every action balanced by its conclusion. Like the yajna described in the Gita where every element is perfectly matched (offering, fire, act), the parentheses algorithm ensures perfect balance through two conditions: open only when capacity remains, close only when something is open. The result is all possible balanced expressions — complete in every arrangement.