Introduction

Generating all well-formed bracket strings is a standard backtracking problem because the search space is large but highly structured. A valid result must stay balanced at every prefix, not only at the end. Once you build the solution around that rule, the algorithm becomes much cleaner than brute-force generation.

Think in Terms of Valid Prefixes

A bracket string is well formed if two conditions hold:

• you never close more brackets than you have opened so far,
• and by the end, the number of opens equals the number of closes.

That means you do not have to generate every possible string of length 2n and test it afterward. You can build the string step by step and reject invalid prefixes immediately.

That pruning idea is the reason backtracking is the usual solution.

Backtracking Is the Most Direct Approach

At any step, you may add an opening bracket if you still have one available. You may add a closing bracket only if it would not make the prefix invalid.

1def generate_brackets(n):
2    result = []
3
4    def backtrack(current, opened, closed):
5        if len(current) == 2 * n:
6            result.append("".join(current))
7            return
8
9        if opened < n:
10            current.append("(")
11            backtrack(current, opened + 1, closed)
12            current.pop()
13
14        if closed < opened:
15            current.append(")")
16            backtrack(current, opened, closed + 1)
17            current.pop()
18
19    backtrack([], 0, 0)
20    return result
21
22print(generate_brackets(3))

This produces:

• '((()))'
• '(()())'
• '(())()'
• '()(())'
• '()()()'

The important property is that the recursion never descends into states that are already invalid.

Why Brute Force Is Wasteful

If you try every length-2n sequence of opening and closing brackets, you create an enormous number of invalid candidates. Most of those strings fail quickly, yet a brute-force generator still spends time constructing them.

Backtracking saves work by encoding the correctness rules directly into the construction process. That does not make the problem easy in an asymptotic sense, because the number of valid results still grows quickly, but it removes a large amount of pointless search.

A Dynamic Programming Perspective Also Exists

There is another way to understand the problem: well-formed bracket strings can be composed from smaller well-formed strings. That leads to a dynamic programming formulation.

If dp[i] stores all valid strings with i pairs, then every result in dp[i] can be formed by wrapping one smaller valid string and concatenating another.

1def generate_brackets_dp(n):
2    dp = [[] for _ in range(n + 1)]
3    dp[0] = [""]
4
5    for i in range(1, n + 1):
6        current = []
7        for left_size in range(i):
8            right_size = i - 1 - left_size
9            for left in dp[left_size]:
10                for right in dp[right_size]:
11                    current.append("(" + left + ")" + right)
12        dp[i] = current
13
14    return dp[n]
15
16print(generate_brackets_dp(3))

This approach is mathematically elegant and useful for understanding the recursive structure of the set. In interviews and day-to-day coding, though, backtracking is usually the simpler implementation.

Generalizing Beyond Parentheses

The same logic extends to other matched delimiters, but you need to be clear about the grammar you want. If there is only one bracket type, the validity rule is simple balance. If you allow multiple bracket types such as parentheses and square brackets, the problem becomes richer because matching type order now matters as well.

So the “well-formed brackets” pattern is a gateway problem for recursive generation more generally.

Complexity Follows the Output Size

The number of valid strings with n pairs is the nth Catalan number. That means the result count itself grows combinatorially. So the algorithm is expensive mainly because there are genuinely many correct answers to emit.

This is an important mindset shift: for enumeration problems, large runtime is often driven by large output, not by a poor algorithm.

Common Pitfalls

• Generating all length-2n strings and validating them afterward instead of pruning during generation.
• Allowing a closing bracket when no unmatched opening bracket exists.
• Forgetting that every completed result must have exactly n opens and n closes.
• Confusing the elegant dynamic-programming formulation with the easiest implementation for production code.
• Treating multiple bracket types as if the single-type balance rule were sufficient.

Summary

• The key idea is to build only valid prefixes.
• Backtracking is the most direct way to generate all well-formed bracket strings.
• Dynamic programming also works and reveals the compositional structure of the problem.
• The number of valid outputs grows according to Catalan numbers.
• Enumeration is expensive because the output set itself becomes large quickly.