Generate Parentheses

Mediumstackbacktrackingrecursion
Category: Stack
Companies that ask this question:
AmazonFacebookGoogleMicrosoft
LeetCode →NeetCode →

Approach

Generate Parentheses

Problem Statement

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

Examples

Example 1

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

Example 2

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

Intuition

A valid parentheses string has these properties:

  1. Equal number of opening '(' and closing ')' brackets
  2. At any point while reading left to right, count of '(' ≥ count of ')'
  3. Every opening bracket has a matching closing bracket

We can build valid strings character by character using backtracking:

  • Add '(' if we haven't used all n opening brackets
  • Add ')' if count of ')' < count of '(' (maintains validity)

Pattern Recognition

This is a Backtracking problem (often visualized with Stack) with:

  • Decision tree exploration
  • Constraints to prune invalid paths
  • Build solution incrementally
  • Backtrack when path becomes invalid

Approach

Use Backtracking with these rules:

  1. Base Case: If string length = 2n, we have a complete valid string
  2. Recursive Cases:
    • Add '(': If openCount < n
      • Recursively continue with openCount + 1
    • Add ')': If closeCount < openCount
      • Recursively continue with closeCount + 1
  3. Track State:
    • Current string being built
    • Count of opening brackets used
    • Count of closing brackets used

Why This Works:

  • We never create invalid strings (')' only added when safe)
  • We explore all possible valid combinations
  • Constraints prevent unnecessary exploration

Edge Cases

  • n = 1 (simplest case: "()")
  • n = 0 (edge case: [""] or [])
  • Large n (exponential growth but pruned by constraints)

Complexity Analysis

  • Time Complexity: O(4^n / √n) - Catalan number
    • Number of valid combinations is the nth Catalan number
    • Each combination requires O(n) time to build
  • Space Complexity: O(n)
    • Recursion depth is at most 2n
    • Each string is length 2n
    • Result list not counted in space complexity

Alternative Approaches

  1. Iterative with Stack: Use explicit stack instead of recursion
  2. Dynamic Programming: Build solutions for n from solutions of n-1

Solution

java
1class Solution {
2    public List<String> generateParenthesis(int n) {
3        List<String> result = new ArrayList<>();
4        backtrack(result, "", 0, 0, n);
5        return result;
6    }
7
8    private void backtrack(List<String> result, String current,
9                          int openCount, int closeCount, int n) {
10        // Base case: we have a complete valid string
11        if (current.length() == 2 * n) {
12            result.add(current);
13            return;
14        }
15
16        // Add opening bracket if we haven't used all n
17        if (openCount < n) {
18            backtrack(result, current + "(", openCount + 1, closeCount, n);
19        }
20
21        // Add closing bracket if it keeps string valid
22        if (closeCount < openCount) {
23            backtrack(result, current + ")", openCount, closeCount + 1, n);
24        }
25    }
26}
27
Loading visualizer...