Generate Parentheses

MEDIUM✓ CHIP-TIMEDLC #22 — FULL STATEMENT ↗

The drill: Build every well-formed way to arrange n pairs of parentheses — a prefix may never have more closes than opens, and the whole string must balance by the end.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A single integer n arrives, standing for n pairs of parentheses. The drill is to produce every distinct string that arranges those pairs into a well-formed sequence.

Well-formed means every opening parenthesis is eventually matched by a closing one, and at no point while reading left to right does the running count of closes exceed the count of opens.

The output is the full set of such strings, each one exactly 2n characters long, with no duplicates and no particular ordering required among them.

EX 01

n = 1

→ ["()"]

MINIMUM SIZE — ONE PAIR, ONE SHAPE

EX 02

n = 2

→ ["(())", "()()"]

TWO PAIRS — NESTED OR SIDE BY SIDE

EX 03

n = 3

→ ["((()))", "(()())", "(())()", "()(())", "()()()"]

FIVE SHAPES — THE BOARD'S USUAL EXAMPLE SIZE

n typically ranges from 1 up to around eight pairs
every returned string has length exactly 2n
no prefix may ever contain more closes than opens
output order among the valid strings doesn't matter

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

At every position you're choosing to place an open or a close paren, but not every choice is legal at every moment. What two counts must you track to know which choices still are?

HINT 2 THE STRUCTURE

Track how many opens and closes you've placed so far. An open is legal whenever you haven't used all n of them; a close is legal only when it wouldn't outnumber the opens already placed.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack: recurse with “(” appended whenever opens < n, and recurse with “)” appended whenever closes < opens. A complete string of length 2n is a valid answer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PRUNED BUILDPATTERN · PRUNED BACKTRACKINGn = 2

STEP 1

n=2: place '(' whenever opens<2, and ')' whenever closes<opens — backtracking prunes the illegal branches automatically.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/generate-parentheses.py — RACE PACE

LANG ▸

PACE ▸

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

        def backtrack(path, opens, closes):
            if len(path) == 2 * n:
                result.append(path)
                return
            if opens < n:
                backtrack(path + "(", opens + 1, closes)
            if closes < opens:
                backtrack(path + ")", opens, closes + 1)

        backtrack("", 0, 0)
        return result

TIME O(4^N / √N)SPACE O(4^N / √N)PYTHON · RACE PACE · 15 LN

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        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 build(path):
            if len(path) == 2 * n:
                if is_valid(path):
                    result.append(path)
                return
            build(path + "(")
            build(path + ")")

        build("")
        return result

TIME O(2^2N · N)SPACE O(2^2N · N)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(new StringBuilder(), 0, 0, n, result);
        return result;
    }

    private void backtrack(StringBuilder path, int opens, int closes, int n, List<String> result) {
        if (path.length() == 2 * n) {
            result.add(path.toString());
            return;
        }
        if (opens < n) {
            path.append('(');
            backtrack(path, opens + 1, closes, n, result);
            path.deleteCharAt(path.length() - 1);
        }
        if (closes < opens) {
            path.append(')');
            backtrack(path, opens, closes + 1, n, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

TIME O(4^N / √N)SPACE O(4^N / √N)JAVA · RACE PACE · 24 LN

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        build("", n, result);
        return result;
    }

    private void build(String path, int n, List<String> result) {
        if (path.length() == 2 * n) {
            if (isValid(path)) {
                result.add(path);
            }
            return;
        }
        build(path + "(", n, result);
        build(path + ")", n, result);
    }

    private boolean isValid(String s) {
        int balance = 0;
        for (char c : s.toCharArray()) {
            balance += c == '(' ? 1 : -1;
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }
}

TIME O(2^2N · N)SPACE O(2^2N · N)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED