22. Generate Parentheses

MediumView on LeetCode

String Backtracking Dynamic Programming

Time: O(4^n/√n)

Space: O(n)

Problem Overview

Every position holds either an opening or a closing parenthesis.

Intuition

Every position holds either an opening or a closing parenthesis. A prefix stays valid as long as no more than n openers are used and closers never outnumber openers. Choosing only moves that keep those two rules means every complete string is already valid, so nothing needs checking afterward. Writing into one shared character buffer and turning it into a string only when it is full avoids copying the prefix on every step.

Algorithm

1Allocate a character buffer of length 2n and presize the result list to the Catalan number of n.
2Recurse with the open and close counts. Their sum is the next position to fill.
3When the buffer is full, add a new string built from it.
4If open is below n, write an opening parenthesis at that position and recurse with open plus one.
5If close is below open, write a closing parenthesis there and recurse with close plus one.

Example Walkthrough

Input: n = 2

1.Position 0 can only take an opening parenthesis, because nothing is open yet.
2.At position 1, another opener leads to (( and then two closers give (()).
3.Choosing a closer at position 1 gives (), and then an opener and a closer give ()().

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

Common Pitfalls

•Allow a closing parenthesis only while close is below open. Checking close against n instead creates strings like ))((.
•The number of answers is the Catalan number, which grows much more slowly than 2 to the power 2n.
•Concatenating a new string at every call copies the prefix each time. Overwriting one buffer position is enough because each level only changes its own slot.
•The output itself has Catalan many strings of length 2n, so no method can run faster than writing them out.

22.cs

// Approach: Backtrack over one shared char buffer of length 2n with two
// counters, open and close. Place '(' while open < n, and place ')' while
// close < open, so only valid prefixes are ever explored. A string is built
// only when the buffer is full, and the result list is presized to the
// Catalan number C(n) = C(2n, n) / (n + 1).
// Time: O(4^n/√n) Space: O(n) recursion and buffer beyond the output

public class Solution
{
    public IList<string> GenerateParenthesis(int n)
    {
        long catalan = 1;
        for (int i = 0; i < n; i++)
            catalan = catalan * 2 * (2 * i + 1) / (i + 2);

        var ans = new List<string>((int)catalan);
        Generate(new char[2 * n], 0, 0, n, ans);
        return ans;
    }

    private static void Generate(char[] buf, int open, int close, int n, List<string> ans)
    {
        int pos = open + close;
        if (pos == buf.Length)
        {
            ans.Add(new string(buf));
            return;
        }

        if (open < n)
        {
            buf[pos] = '(';
            Generate(buf, open + 1, close, n, ans);
        }
        if (close < open)
        {
            buf[pos] = ')';
            Generate(buf, open, close + 1, n, ans);
        }
    }
}

Was this solution helpful?