Generate Balanced Parentheses

1. Step 1: Initialize Solution.generateParenthesis

   Replace the empty starter with the first real state owned by Solution.generateParenthesis. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Pass the One Pair case

   Complete the readable core algorithm for one representative Interview case. Prune invalid prefixes by tracking available opening and closing choices.

3. Step 3: Harden the Two Pairs boundary

   Repair the reviewed boundary and pass the complete submission contract. Every explored prefix is balanced because closes never exceed opens; every balanced length-2n string follows one permitted sequence of choices and is emitted once.

• A closing parenthesis is legal only when more opens than closes have already been used.
• recursion and backtracking

• LeetCode 22 — Generate Parentheses
• Hello Interview — Backtracking Overview

• Complete One Backtracking Frame(opens in a new tab)

  Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing generate parentheses as a complete Interview Problem.

Backtrack with counts of used opens and closes, adding an open below n and a close only below the open count.

Why it works: Every explored prefix is balanced because closes never exceed opens; every balanced length-2n string follows one permitted sequence of choices and is emitted once.

class Solution:
    def generateParenthesis(self, n):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        result = []
        path = []
        def backtrack(opened, closed):
            if len(path) == 2 * n:
                result.append(''.join(path))
                return
            if opened < n:
                path.append('(')
                backtrack(opened + 1, closed)
                path.pop()
            if closed < opened:
                path.append(')')
                backtrack(opened, closed + 1)
                path.pop()
        backtrack(0, 0)
        return result

• Phone Keypad Letter Combinations(opens in a new tab)