Generate Parentheses

Difficulty: Medium Source: NeetCode

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion — understanding how a function calls itself with modified state
• Backtracking — building a candidate solution step by step and undoing choices when a branch is invalid

1. Brute Force

Intuition

Generate every possible string of length 2n made up of ( and ) characters, then filter out the invalid ones. A string is valid if at no prefix does the count of ) exceed the count of (, and both counts are equal at the end. This works but wastes a lot of time building strings we immediately throw away.

Algorithm

1. Generate all 2^(2n) strings of length 2n using ( and ).
2. For each string, check if it is a valid parentheses sequence.
3. Collect and return all valid strings.

Solution

def generateParenthesis_brute(n: int):
    result = []

    def is_valid(s):
        balance = 0
        for c in s:
            balance += 1 if c == '(' else -1
            if balance < 0:
                return False
        return balance == 0

    def generate(current):
        if len(current) == 2 * n:
            if is_valid(current):
                result.append(current)
            return
        generate(current + '(')
        generate(current + ')')

    generate("")
    return result


print(generateParenthesis_brute(3))
# ["((()))","(()())","(())()","()(())","()()()"]
print(generateParenthesis_brute(1))
# ["()"]

Complexity

• Time: O(2^(2n) * n) — generate all strings, validate each one
• Space: O(n) — recursion depth

2. Backtracking

Intuition

Instead of generating everything and filtering, we build the string character by character and only ever add a character that keeps the sequence valid. The two rules are: add ( if we still have open parentheses left to place (open < n), and add ) if the number of close brackets placed so far is less than the number of open brackets placed (close < open). When the string reaches length 2n it is guaranteed to be valid — no filtering needed.

Algorithm

1. Start with an empty string, open = 0, close = 0.
2. If len(current) == 2 * n, add current to results and return.
3. If open < n, recurse with ( appended and open + 1.
4. If close < open, recurse with ) appended and close + 1.

Solution

def generateParenthesis(n: int):
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)

    backtrack("", 0, 0)
    return result


print(generateParenthesis(3))
# ["((()))","(()())","(())()","()(())","()()()"]
print(generateParenthesis(1))
# ["()"]
print(generateParenthesis(2))
# ["(())", "()()"]

Complexity

• Time: O(4^n / sqrt(n)) — the nth Catalan number counts valid sequences
• Space: O(n) — recursion depth is at most 2n

Common Pitfalls

Adding ) without enough open brackets. If you don’t guard close < open, you’ll generate strings like )( which are never valid. Always check this condition before adding a closing bracket.

Checking validity at the end instead of pruning early. The brute force approach checks validity only after building the full string. The backtracking approach avoids entire subtrees by never placing an invalid character — this is the core win.

Passing a mutable list as the “current” string. Using a list and joining at the end is slightly more efficient in Python than string concatenation (current + '('), but either works correctly. If you use a list, remember to pop() after each recursive call to undo the choice.