22. Generate Parentheses - Explanation

Description

You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.

Example 1:

Input: n = 1

Output: ["()"]

Example 2:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

You may return the answer in any order.

Constraints:

1 <= n <= 7

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(4^n / sqrt(n)) time and O(n) space, where n is the number of parenthesis pairs in the string.

Hint 1

A brute force solution would be to generate all possible strings of size 2n and add only the valid strings. This would be an O(n * 2 ^ (2n)) solution. Can you think of a better way? Maybe you can use pruning to avoid generating invalid strings.

Hint 2

We can use backtracking with pruning. But what makes a string invalid? Can you think of a condition for this?

Hint 3

When the count of closing brackets exceeds the count of opening brackets, the string becomes invalid. Therefore, we can maintain two variables, open and close, to track the number of opening and closing brackets. We avoid exploring paths where close > open. Once the string length reaches 2n, we add it to the result.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

Generate all strings of length 2n using only '(' and ')'.
Most will be invalid, so for each completed string we validate it:

Keep a balance (opens count).
'(' increases balance, ')' decreases it.
If balance ever becomes negative, there are too many ) early, which is invalid.
At the end, balance must be 0, meaning all opens are closed.

Algorithm

Use DFS to build a string s.
If len(s) == 2n, check if s is valid using the balance rule:
- If valid, add to result.
Otherwise, branch:
- Try adding '('.
- Try adding ')'.
Return the collected results.

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

        def valid(s: str):
            open = 0
            for c in s:
                open += 1 if c == '(' else -1
                if open < 0:
                    return False
            return not open

        def dfs(s: str):
            if n * 2 == len(s):
                if valid(s):
                    res.append(s)
                return

            dfs(s + '(')
            dfs(s + ')')

        dfs("")
        return res

Time & Space Complexity

Time complexity: $O(2 ^ {2n} * n)$
Space complexity: $O(2 ^ {2n} * n)$

2. Backtracking

Intuition

Instead of generating all strings and then checking validity, we build only valid strings.

Key rules for valid parentheses:

You can add '(' only if you still have openings left (open < n).
You can add ')' only if it won't break validity (close < open).
A string is complete and valid only when open == close == n.

So at every step, we make safe choices only, which avoids invalid paths early.

Algorithm

Start with an empty string.
Track:
- open - number of '(' used.
- close - number of ')' used.
If open == close == n, add the built string to the result.
If open < n, add '(' and recurse.
If close < open, add ')' and recurse.
Backtrack after each choice.

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

        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return

            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()

        backtrack(0, 0)
        return res

Time & Space Complexity

Time complexity: $O(\frac{4^n}{\sqrt{n}})$
Space complexity: $O(n)$

3. Dynamic Programming

Intuition

A valid parentheses string can be built from smaller valid strings.

Think of this pattern: ( left ) right

left is a valid parentheses string with i pairs.
right is a valid parentheses string with k - i - 1 pairs.
Wrapping left with () guarantees balance.
Appending right keeps the string valid.

So, every valid result for k pairs is formed by combining smaller answers.

Algorithm

Let dp[x] store all valid parentheses strings with x pairs.
Base case:
- dp[0] = [""] (empty string).
For each k from 1 to n:
- Try all splits i from 0 to k-1.
- Combine:
```
"(" + dp[i] + ")" + dp[k - i - 1]
```
Store all combinations in dp[k].
Return dp[n].

class Solution:
    def generateParenthesis(self, n):
        res = [[] for _ in range(n+1)]
        res[0] = [""]

        for k in range(n + 1):
            for i in range(k):
                for left in res[i]:
                    for right in res[k-i-1]:
                        res[k].append("(" + left + ")" + right)

        return res[-1]

Time & Space Complexity

Time complexity: $O(\frac{4^n}{\sqrt{n}})$
Space complexity: $O(n)$

Common Pitfalls

Using Wrong Condition for Adding Closing Parenthesis

The condition to add ) is close < open, not close < n. Adding a closing parenthesis is only valid when there are unmatched opening parentheses. Using close < n would generate invalid strings like ())(() where closing brackets appear before their matching opens.

Forgetting to Backtrack When Using a Mutable Builder

When using a mutable structure like a list or StringBuilder to build the string, you must remove the last character after the recursive call returns. Forgetting to pop/remove leads to corrupted strings in subsequent branches. The immutable string concatenation approach avoids this issue but is less memory efficient.

Misunderstanding the Base Case Condition

The base case should check open == n && close == n, not just length == 2n. While both conditions are mathematically equivalent for valid paths, explicitly checking both counters makes the logic clearer and helps catch bugs where invalid strings might reach length 2n through incorrect branching conditions.