Generate Parentheses

Medium Problem 91 of 151 Java and Python

Practice on LeetCode

Problem

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

Example 1

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

Example 2

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

Constraints

1 ≤ n ≤ 8

Explanation

You could generate all 2²ⁿ strings and keep the valid ones, but most are invalid.

Instead only build valid prefixes: you may add ( while fewer than n have been used, and ) while there are more opens than closes so far. Every completed string is then valid.

Approach 1 · Naive

Generate all, filter valid

Time O(2²ⁿ · n)
Space O(n) recursion besides the output

Build every string of length 2n from ( and ), and keep the balanced ones.

Recursively build all 2²ⁿ strings.
Keep a string if its running balance never drops below 0 and ends at 0.

Java

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        build(new char[2 * n], 0, result);
        return result;
    }

    private void build(char[] s, int pos, List<String> result) {
        if (pos == s.length) {
            if (valid(s)) {
                result.add(new String(s));
            }
            return;
        }
        s[pos] = '(';
        build(s, pos + 1, result);
        s[pos] = ')';
        build(s, pos + 1, result);
    }

    private boolean valid(char[] s) {
        int balance = 0;
        for (char c : s) {
            balance += c == '(' ? 1 : -1;
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }
}

Python

from itertools import product

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def valid(s):
            balance = 0
            for c in s:
                balance += 1 if c == "(" else -1
                if balance < 0:
                    return False
            return balance == 0

        return ["".join(s) for s in product("()", repeat=2 * n) if valid(s)]

Approach 2 · Optimal

Backtracking with open and close counts

Time O(4ⁿ / √n), the Catalan number of results
Space O(n) recursion besides the output

Add ( if open < n; add ) if close < open. Record the string when it reaches length 2n.

backtrack(open, close): if the path has 2n characters, record it.
If open < n, add ( and recurse.
If close < open, add ) and recurse.

Java

import java.util.*;

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

    private void backtrack(int n, int open, int close, StringBuilder path, List<String> result) {
        if (path.length() == 2 * n) {
            result.add(path.toString());
            return;
        }
        if (open < n) {
            path.append('(');
            backtrack(n, open + 1, close, path, result);
            path.deleteCharAt(path.length() - 1);
        }
        if (close < open) {
            path.append(')');
            backtrack(n, open, close + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

Python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result, path = [], []

        def backtrack(open_count, close_count):
            if len(path) == 2 * n:
                result.append("".join(path))
                return
            if open_count < n:
                path.append("(")
                backtrack(open_count + 1, close_count)
                path.pop()
            if close_count < open_count:
                path.append(")")
                backtrack(open_count, close_count + 1)
                path.pop()

        backtrack(0, 0)
        return result

Complexity compared

Approach	Time	Space
Naive Generate all, filter valid	O(2²ⁿ · n)	O(n) recursion besides the output
Optimal Backtracking with open and close counts	O(4ⁿ / √n), the Catalan number of results	O(n) recursion besides the output

Key takeaways

Pruning invalid prefixes early is the difference between "generate and test" and real backtracking.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem