Generate Parentheses

Problem Description

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

Examples

Constraints

• 1 <= n <= 8

Backtracking Search with Balance Rules

To generate only well-formed parentheses (avoiding checking all 2^(2n) random bracket strings), we use backtracking. We build the string character by character. We keep track of the number of open and close parentheses used so far. We can add an open parenthesis ( if open < n. We can add a close parenthesis ) if close < open (which ensures every closing bracket matches a preceding open bracket). When the string reaches length 2 * n, we add it to our results.

Solution 1: Backtracking String Building

Build valid combinations recursively while maintaining parenthesis balance counters.

import java.util.ArrayList;
import java.util.List;

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 max) {
        if (sb.length() == max * 2) {
            res.add(sb.toString());
            return;
        }

        if (open < max) {
            sb.append("(");
            backtrack(res, sb, open + 1, close, max);
            sb.deleteCharAt(sb.length() - 1); // backtrack
        }
        if (close < open) {
            sb.append(")");
            backtrack(res, sb, open, close + 1, max);
            sb.deleteCharAt(sb.length() - 1); // backtrack
        }
    }
}

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        res = []
        
        def backtrack(curr_str: list[str], open_count: int, close_count: int):
            if len(curr_str) == n * 2:
                res.append("".join(curr_str))
                return
                
            if open_count < n:
                curr_str.append("(")
                backtrack(curr_str, open_count + 1, close_count)
                curr_str.pop()  # backtrack
                
            if close_count < open_count:
                curr_str.append(")")
                backtrack(curr_str, open_count, close_count + 1)
                curr_str.pop()  # backtrack

        backtrack([], 0, 0)
        return res

#include <vector>
#include <string>

class Solution {
private:
    void backtrack(std::vector<std::string>& res, std::string& current, int open, int close, int n) {
        if (current.length() == n * 2) {
            res.push_back(current);
            return;
        }

        if (open < n) {
            current.push_back('(');
            backtrack(res, current, open + 1, close, n);
            current.pop_back(); // backtrack
        }
        if (close < open) {
            current.push_back(')');
            backtrack(res, current, open, close + 1, n);
            current.pop_back(); // backtrack
        }
    }

public:
    std::vector<std::string> generateParenthesis(int n) {
        std::vector<std::string> res;
        std::string current = "";
        backtrack(res, current, 0, 0, n);
        return res;
    }
};

Complexity Analysis

• Time Complexity: O(4ⁿ / √n) which is bounded by the Catalan number, representing the count of valid combinations.
• Space Complexity: O(n) auxiliary space to store recursion frames.

Where It Breaks

If n grows large (e.g., n > 15), the total combinations grow exponentially, exhausting memory bounds when collecting the final result list.

Common Mistakes

• Incorrect backtracking string updates: Forgetting to pop the last character from the string builder or list after returning from the recursive call. This causes state contamination across branches.
• Flawed branch condition: Allowing closing brackets when close <= open instead of close < open. This produces illegal strings like ())(.

Frequently Asked Questions

What are Catalan numbers? The sequence of Catalan numbers directly represents the number of valid parenthesized expressions. For n = 3, the 3rd Catalan number is 5, which matches the length of the result list.

Why does checking close < open guarantee validity? At any index, the number of closing brackets cannot exceed the number of opening brackets. This is the defining condition of a prefix to a valid parenthesis string.

← All Problems