Generate Parentheses

Problem Statement

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

What to notice first

• A valid parenthesis string has equal numbers of ( and ).
• At any point while building, open count must be >= close count.
• You can only add ( if open < n.
• You can only add ) if close < open.

Examples

n	Output	Count
1	["()"]	1
2	["(())","()()"]	2
3	["((()))","(()())","(())()","()((})","()()()"]	5

Constraints

• 1 <= n <= 8
• The number of well-formed strings grows as the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!)

Real-World Applications

Where this pattern appears

• Syntax parsing — generating all valid parse trees for expressions with balanced operators.
• Code generation — validating and generating code with nested blocks and scopes.
• Mathematical combinations — counting/generating all valid nested structure combinations.
• Compiler design — checking well-formed nested structures in language parsing.

Complexity Comparison

Approach	Time	Space	Notes
Backtracking	O(4^n / √n)	O(n)	Prunes invalid paths early; intuitive recursion
Dynamic Programming	O(4^n / √n)	O(n)	Builds bottom-up; combines subproblems

Both approaches have the same asymptotic complexity (Catalan number), but backtracking prunes earlier.

Approach 1: Backtracking (Recommended)

★ Recommended

Use backtracking to generate parentheses recursively. At each step, decide whether to add an opening or closing parenthesis:

• Add ( if we have fewer than n opening parentheses.
• Add ) if we have fewer closing than opening parentheses (maintains validity).

This prunes invalid paths immediately, making it more efficient than brute force.

⏱ Time O(4^n / √n) Catalan number growth 💾 Space O(n) Recursion depth + result

Step-by-step Example

Input: n = 2

Start: ""
├─ Add '(': "("
│  ├─ Add '(': "(("
│  │  └─ Add ')': "(()"
│  │     └─ Add ')': "(())"  ✓
│  └─ Add ')': "()"
│     └─ Add '(': "()("
│        └─ Add ')': "()()"  ✓
└─ Can't add ')' yet (left == 0)

Result: ["(())", "()()"]

Pseudocode

function generateParenthesis(n):
    result = []

    def backtrack(current, leftCount, rightCount):
        if len(current) == 2 * n:
            result.append(current)
            return

        if leftCount < n:
            backtrack(current + "(", leftCount + 1, rightCount)

        if rightCount < leftCount:
            backtrack(current + ")", leftCount, rightCount + 1)

    backtrack("", 0, 0)
    return result

Solution Code

Python

generate_parentheses_backtracking.py

from typing import List

def generateParenthesis(n: int) -> List[str]:
    """Backtracking approach: O(4^n) time, O(n) space"""
    result = []

    def backtrack(current, left, right):
        if len(current) == 2 * n:
            result.append(current)
            return
        if left < n:
            backtrack(current + "(", left + 1, right)
        if right < left:
            backtrack(current + ")", left, right + 1)

    backtrack("", 0, 0)
    return result

C++

generate_parentheses_backtracking.cpp

#include <vector>
#include <string>
using namespace std;

vector<string> generateParenthesis(int n) {
    vector<string> result;

    function<void(string, int, int)> backtrack = [&](string current, int left, int right) {
        if (current.length() == 2 * n) {
            result.push_back(current);
            return;
        }
        if (left < n) backtrack(current + "(", left + 1, right);
        if (right < left) backtrack(current + ")", left, right + 1);
    };

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

Java

GenerateParenthesesBacktracking.java

import java.util.*;

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

    private void backtrack(List<String> result, String current, int left, int right, int n) {
        if (current.length() == 2 * n) {
            result.add(current);
            return;
        }

        if (left < n) {
            backtrack(result, current + "(", left + 1, right, n);
        }

        if (right < left) {
            backtrack(result, current + ")", left, right + 1, n);
        }
    }
}

JavaScript

generate_parentheses_backtracking.js

function generateParenthesis(n) {
    const result = [];

    function backtrack(current, left, right) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        if (left < n) backtrack(current + "(", left + 1, right);
        if (right < left) backtrack(current + ")", left, right + 1);
    }

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

Rust

generate_parentheses_backtracking.rs

pub fn generate_parenthesis(n: i32) -> Vec<String> {
    let mut result = Vec::new();
    fn backtrack(result: &mut Vec<String>, current: String, left: i32, right: i32, n: i32) {
        if current.len() == (2 * n) as usize {
            result.push(current);
            return;
        }
        if left < n {
            backtrack(result, current.clone() + "(", left + 1, right, n);
        }
        if right < left {
            backtrack(result, current + ")", left, right + 1, n);
        }
    }
    backtrack(&mut result, String::new(), 0, 0, n);
    result
}

Go

generate_parentheses_backtracking.go

package main

func generateParenthesis(n int) []string {
    result := []string{}
    backtrack(&result, "", 0, 0, n)
    return result
}

func backtrack(result *[]string, current string, left, right, n int) {
    if len(current) == 2*n {
        *result = append(*result, current)
        return
    }
    if left < n {
        backtrack(result, current+"(", left+1, right, n)
    }
    if right < left {
        backtrack(result, current+")", left, right+1, n)
    }
}

Approach 2: Dynamic Programming

✓ Simple

Build valid parentheses combinations bottom-up. For i pairs, insert all valid combinations of j pairs inside parentheses, then append all valid combinations of remaining (i-1-j) pairs.

The recurrence: DP[i] = "(" + DP[j] + ")" + DP[i-1-j] for all valid j.

⏱ Time O(4^n / √n) Catalan number 💾 Space O(n) DP table + recursion

Step-by-step Example

Input: n = 2

DP[0] = [""]
DP[1] = ["()"]        (from: "(" + DP[0] + ")" + DP[0])
DP[2] = [
  "(" + "()" + ")" + "" = "(())",
  "(" + "" + ")" + "()" = "()()"
]

Pseudocode

function generateParenthesis(n):
    dp = [[] for _ in range(n + 1)]
    dp[0] = [""]

    for i in range(1, n + 1):
        for j in range(i):
            for left in dp[j]:
                for right in dp[i - 1 - j]:
                    dp[i].append("(" + left + ")" + right)

    return dp[n]

Solution Code

Python

generate_parentheses_dp.py

from typing import List

def generateParenthesis(n: int) -> List[str]:
    """DP approach: O(4^n) time, O(n) space"""
    if n == 0:
        return [""]
    dp = [[] for _ in range(n + 1)]
    dp[0] = [""]

    for i in range(1, n + 1):
        for j in range(i):
            for left in dp[j]:
                for right in dp[i - 1 - j]:
                    dp[i].append("(" + left + ")" + right)

    return dp[n]

C++

generate_parentheses_dp.cpp

#include <vector>
#include <string>
using namespace std;

vector<string> generateParenthesis(int n) {
    vector<vector<string>> dp(n + 1);
    dp[0] = {""};

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            for (const auto& left : dp[j]) {
                for (const auto& right : dp[i - 1 - j]) {
                    dp[i].push_back("(" + left + ")" + right);
                }
            }
        }
    }

    return dp[n];
}

Java

GenerateParenthesesDP.java

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }
        dp.get(0).add("");

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                for (String left : dp.get(j)) {
                    for (String right : dp.get(i - 1 - j)) {
                        dp.get(i).add("(" + left + ")" + right);
                    }
                }
            }
        }

        return dp.get(n);
    }
}

JavaScript

generate_parentheses_dp.js

function generateParenthesis(n) {
    const dp = Array(n + 1).fill(null).map(() => []);
    dp[0] = [""];

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            for (const left of dp[j]) {
                for (const right of dp[i - 1 - j]) {
                    dp[i].push("(" + left + ")" + right);
                }
            }
        }
    }

    return dp[n];
}

Rust

generate_parentheses_dp.rs

pub fn generate_parenthesis(n: i32) -> Vec<String> {
    let n = n as usize;
    let mut dp = vec![vec![]; n + 1];
    dp[0] = vec!["".to_string()];

    for i in 1..=n {
        for j in 0..i {
            for left in &dp[j] {
                for right in &dp[i - 1 - j] {
                    dp[i].push(format!("({}){}", left, right));
                }
            }
        }
    }

    dp[n].clone()
}

Go

generate_parentheses_dp.go

package main

func generateParenthesis(n int) []string {
    dp := make([][]string, n+1)
    dp[0] = []string{""}

    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            for _, left := range dp[j] {
                for _, right := range dp[i-1-j] {
                    dp[i] = append(dp[i], "("+left+")"+right)
                }
            }
        }
    }

    return dp[n]
}

Common Mistakes

Watch for these pitfalls

• Forgetting the closing parenthesis condition: You must check rightCount < leftCount to avoid closing before opening.
• Base case logic: Ensure len(current) == 2 * n is the termination condition.
• DP indexing: Ensure loop bounds and DP table initialization are correct (off-by-one errors).
• String building: In languages like Java, use StringBuilder for efficiency to avoid O(n) concatenation overhead.

Interview Tips

Key trade-offs to discuss

• Backtracking vs. DP: Backtracking is more intuitive and prunes early. DP is more algorithmic and bottom-up.
• Why Catalan numbers? The nth Catalan number counts all valid parenthesis combinations; knowing this helps validate your result count.
• Follow-up: Can you count the solutions without generating them? (Yes—just return DP[n].length or count during recursion.)
• Space optimization: Neither approach reduces space below O(n) because the output itself is exponential.