Generate Parentheses

MediumBacktrackingNeetCode 150MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an integer n. Return every string made of n "(" characters and n ")" characters that is well-formed: reading left to right, each ")" closes an earlier "(" that is still open, and every "(" is closed by the end. Each string has length 2n and must appear exactly once. The list may be in any order.

Examples

n = 3 returns ["((()))","(()())","(())()","()(())","()()()"]

These are the only five ways to arrange three matched pairs. A string like "())(()" is left out because its third character closes a pair that was never opened.

n = 1 returns ["()"]

With a single pair, "()" is the only option, since ")(" closes before anything is open.

Constraints

1 <= n <= 8

Hints

Hint 1

Every valid string is built by appending either '(' or ')', when is each of those legal?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Build strings one character at a time and only make moves that keep the prefix valid. You may add "(" while fewer than n have been used, and ")" only while close < open, so every ")" has an open "(" to match. A path that reaches length 2n is therefore complete and valid, so record it. Invalid prefixes are never extended, so the work tracks the number of answers: the n-th Catalan number, roughly 4^n / n^1.5 strings of length 2n.

Time

O(4^n / sqrt(n))

Space

O(n)

Pitfall

Allowing ")" whenever close < n, instead of close < open, lets invalid strings like "())(()" through. Generating all 2^(2n) strings and filtering the valid ones works but does far more work than needed.

Solutions

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);
        }
    }
}

class Solution:
    def generateParenthesis(self, n: int):
        result = []

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

        backtrack(0, 0, [])
        return result