Generate Parentheses Explained: Tracing n = 3 Valid Combinations

Imagine you need to generate every possible arrangement of matching parentheses for a given pair count $n=3$. If you attempt this with a brute-force permutation generator, you quickly run into a wall of structural invalidity. For $n=3$, there are 6 total characters (3 opening ( and 3 closing )), which yields $2^6=64$ binary choices or $6!=720$ raw permutations depending on how you model the slots. Most of those combinations are completely malformed, such as )()()( or )))(((, where closing brackets appear before they have any matching openers.

Without a constrained generation strategy, your code wastes massive CPU cycles filtering out garbage strings after the fact. The core problem of generate parentheses is not just counting characters, but ensuring that at every single index along the string, the number of closing parentheses never exceeds the number of opening ones. We need a systematic way to build strings character by character so that illegal states are pruned before they ever materialize.

# Given: n = 3 pairs of parentheses
# Goal: Produce the complete list of 5 valid strings:
# ["((()))", "(()())", "(())()", "()(())", "()()()"]
# Question: Why does a naive permutation approach fail to scale for larger n?

When we want to generate all valid strings for $n=3$ pairs of parentheses, we can visualize the process as walking down a decision tree. At every single step of building our string, we have a choice: do we append an open parenthesis ( or a close parenthesis )?

However, we cannot make these choices blindly, or we end up with invalid sequences like )( or (()))(. To make this rigorous, our mental model must track two running integers as state: openUsed (how many ( we have placed so far) and closeUsed (how many ) we have placed so far).

Instead of generating all $2^{2n}$ possible bitstrings of length 6 (which is 64 combinations for $n=3$) and filtering them later, our recursive model prunes invalid branches instantly. We impose two strict structural guardrails on any path:

1. The Open Guard: We can only add an open parenthesis ( if our current openUsed count is strictly less than $n$. For $n=3$, we can place at most three ( characters total.
2. The Close Guard: We can only add a close parenthesis ) if our current closeUsed count is strictly less than openUsed. This ensures a ) never precedes its matching (.

Start: (open=0, close=0, path="")
├── Add '(' -> (open=1, close=0, path="(")
│ ├── Add '(' -> (open=2, close=0, path="((")
│ │ └── ...
│ └── Add ')' -> (open=1, close=1, path="()")
└── Add ')' -> BLOCKED (close >= open)

As we trace down this tree for $n=3$, every time our path reaches a length of $2n$ (meaning 3 opens and 3 closes), we have successfully constructed one of our target items, such as (())(). The model turns a messy combinatorial search into a clean, depth-first traversal of valid states.

To see our recursive tree model in action, let us trace the execution for $n=3$. We maintain three variables in our function signature: openUsed (count of open brackets used so far), closeUsed (count of close brackets used so far), and path (the current string being constructed). When both openUsed and closeUsed equal $n$, our path reaches length 6 and we collect it into our results array.

- Target pair count: $n=3$
- Initial state: openUsed = 0, closeUsed = 0, `path =

Now that you have seen how the algorithm builds all 5 valid strings for $n=3$, it is time to test your mental model on a smaller instance. Consider running the same backtracking function with $n=2$.

Recall the two core rules established in the recursive tree model:
- You may append an opening parenthesis ( if your current openCount < n.
- You may append a closing parenthesis ) if your current closeCount < openCount.

Take out a piece of paper or open a scratchpad and trace out the exact sequence of states (open, close, path) starting from (0, 0, "") until you hit the base length of $2n=4$.

1. Write down the complete list of valid strings generated when $n=2$.
2. How many total leaves (both valid and invalid pruned branches) does the recursion tree visit for $n=2$?
3. Verify why a state like open = 1, close = 2 is immediately pruned by the second rule.

# Try tracing n = 2 manually or write a quick check:
# n = 2 expected output size is 2 strings.

Now that you have traced how the backtracking state machine builds the 5 valid strings for $n=3$ (from ((())) down to ()()()), you can apply this exact decision-tree pattern to kindred structural generation problems. The core rule we established—only taking branches that maintain structural validity at every step—remains identical when the alphabet or limits change.

Consider a variant where you must generate all valid combinations of $n$ pairs of mixed brackets, such as () and [], or a problem counting unique binary search trees with $n$ nodes, which follows the exact same Catalan number sequence. In each case, your mental model shifts from simple brute-force loops to managing explicit validity invariants during recursion.

When facing a new generation problem, ask yourself three questions derived from our backtracking model:

1. What constitutes a single incremental decision (like adding ()?

By mapping these questions to your working knowledge of openUsed and closeUsed, you avoid writing redundant validation checks at the end of every recursion branch.

def generateParenthesisVariant(n):
    # TODO: Apply the open/close tracking pattern
    # to generate strings under a modified constraint.
    pass