22. Generate Parentheses

Time: O(4^n/√n)

Space: O(n)

Intuition

At each position in the string we have at most two choices: place "(" or ")". The constraints - open count <= n and close count <= open count - automatically prune all invalid branches, so every leaf of the recursion tree is already a valid string. No post-validation is needed.

Algorithm

1Recurse with state: (currentString, openCount, closeCount).
2Base case: if currentString.Length == 2*n, add it to results.
3If openCount < n: recurse with "(" appended and openCount+1.
4If closeCount < openCount: recurse with ")" appended and closeCount+1.

Example Walkthrough

Input: n = 2

1.Start: ("", 0, 0). Can add "(" -> ("(", 1, 0).
2.From ("(", 1, 0): add "(" -> ("((", 2, 0) or add ")" -> ("()", 1, 1).
3.From ("((", 2, 0): can only add ")" -> ("(()", 2, 1) -> ("(())", 2, 2) .
4.From ("()", 1, 1): add "(" -> ("()(", 2, 1) -> ("()()", 2, 2) .

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

Common Pitfalls

•Do not use close < n as the condition for adding ")". Use close < open - otherwise you generate invalid strings like "))(".
•The total valid combinations equal the Catalan number C(n), not 2^(2n).

22.cs

// Approach: Backtracking with two counters — open ('(' placed) and close (')' placed).
// At each step, append '(' if open < n (more opening brackets are allowed),
// or append ')' if close < open (there is an unclosed bracket to close).
// A complete string is added to the result when both counters equal n.
// This generates only valid strings without any post-validation — invalid paths are never explored.
// The total number of valid combinations is the n-th Catalan number C(n) = C(2n,n)/(n+1).
// Time: O(4^n/√n) Space: O(n) per path in the recursion stack

public class Solution
{
    public IList<string> GenerateParenthesis(int n)
    {
        IList<string> dp = new List<string>();
        Generate(0, n, 0, 0, "", dp);
        return dp;
    }

    private void Generate(int ind, int n, int op, int cl, string res, IList<string> ans)
    {
        if (op < cl || op > n || cl > n)
            return;

        if (ind == 2 * n)
        {
            ans.Add(res);
            return;
        }

        Generate(ind + 1, n, op + 1, cl, res + '(', ans);
        Generate(ind + 1, n, op, cl + 1, res + ')', ans);
    }
}

Was this solution helpful?