Generate Parentheses

How it works

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.

Steps

1. Let dp[x] store all valid parentheses strings with x pairs.
2. Base case:
   • dp[0] = [""] (empty string).
3. For each k from 1 to n:
   • Try all splits i from 0 to k-1.
   • Combine:

Complexity

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

Things to watch for

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.

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]

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> res(n + 1);
        res[0] = {""};

        for (int k = 0; k <= n; ++k) {
            for (int i = 0; i < k; ++i) {
                for (const string& left : res[i]) {
                    for (const string& right : res[k - i - 1]) {
                        res[k].push_back("(" + left + ")" + right);
                    }
                }
            }
        }

        return res[n];
    }
};