Course4all
Join us on telegram
Home/dsa/Stack/Generate Parentheses

Generate Parentheses

Master this topic with zero to advance depth.

Generate Parentheses

The Catalan Connection

The number of valid strings with n pairs of parentheses is the n-th Catalan Number: Cn=1n+1(2nn)C_n = \frac{1}{n+1} \binom{2n}{n}. This grows roughly as 4n/(nn)4^n / (n \sqrt{n}).

Validity Conditions

A prefix of a parenthesis string is valid if and only if:

  1. Balance: At any point, the number of closing brackets ) does not exceed the number of opening brackets (.
  2. Target: The total number of opening brackets does not exceed n.
  3. Finality: The total length is 2n and the final counts of ( and ) are equal.

Search Space Pruning

Instead of generating all 22n2^{2n} sequences and checking them, we only explore branches that satisfy the balance conditions.

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

Medium

Examples

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

Level I: Brute Force (Generate and Validate)

Intuition

Generate all possible strings of length 2n consisting of '(' and ')'. Check each string for validity using a stack or a counter.

Use recursion to generate all 22n2^{2n} sequences. For each sequence, verify if the balance ever goes negative and ends at zero.

⏱ O(2^{2n} * n)💾 O(n) for recursion depth.

Detailed Dry Run

n=1 Sequences: "((" (Invalid), "()" (Valid), ")(" (Invalid), "))" (Invalid).

java
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }
    private void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) result.add(new String(current));
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }
    private boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') balance++; else balance--;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
}
Approach 2

Level II: Optimized Backtracking (Keeping Balance)

Intuition

Only add a parenthesis if it keeps the sequence valid. We only add '(' if we haven't used n of them, and only add ')' if the number of ')' is less than the number of '('.

Maintain open and close counts. If open < n, we can branch with '('. If close < open, we can branch with ')'.

⏱ O(4^n / \sqrt{n})💾 O(n) recursion depth.

Detailed Dry Run

n=2

  • "(" (open=1, close=0)
    • "((" (open=2, close=0)
      • "(()" (open=2, close=1)
        • "(())" (open=2, close=2) -> SUCCESS
    • "()" (open=1, close=1)
      • "()(" (open=2, close=1)
        • "()()" (open=2, close=2) -> SUCCESS
java
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }
    private void backtrack(List<String> res, StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
            return;
        }
        if (open < n) {
            sb.append('('); backtrack(res, sb, open + 1, close, n); sb.setLength(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')'); backtrack(res, sb, open, close + 1, n); sb.setLength(sb.length() - 1);
        }
    }
}
Approach 3

Level III: Closure Number (Divide and Conquer)

Intuition

Every non-empty valid string S can be uniquely written as (A)B, where A and B are valid (potentially empty) parenthesis strings.

To generate all strings of length 2n, we iterate over all possible lengths of A. For a fixed i, where i is the number of pairs in A, we have n-i-1 pairs in B.

⏱ O(4^n / \sqrt{n})💾 O(4^n / \sqrt{n})

Detailed Dry Run

n=2

  • i=0: (empty) B where B is len 1. Results: "()()"
  • i=1: (len 1) empty. Results: "(())"
java
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            res.add("");
        } else {
            for (int i = 0; i < n; i++) {
                for (String left : generateParenthesis(i)) {
                    for (String right : generateParenthesis(n - i - 1)) {
                        res.add("(" + left + ")" + right);
                    }
                }
            }
        }
        return res;
    }
}
← Previous QuestionSimplify Path
Next Question →Asteroid Collision