Every way the brackets can balance

Given n, list every string of n opening and n closing brackets that is correctly balanced.

Print them in the order the walk produces, which is: at every step try ( before ).

Worked example#

For n = 3 there are five:

((()))
(()())
(())()
()(())
()()()

The idea#

The lazy version writes down all two-to-the-power-of-2n strings and then tests each one. For n = 8 that is 65,536 strings of which only 1,430 are valid, so almost all the work is thrown away.

Backtracking lets you never build a bad one in the first place. At each position there are two choices, and each has a condition:

• Add ( if you have not already used all n of them.
• Add ) if there are more opening brackets so far than closing ones.

That second condition is the whole problem. A closing bracket needs something open to close, and counting is enough to know: if closed has caught up with opened, a ) here would close nothing.

walk(built, opened, closed):
    if built is 2n long: record it, return
    if opened < n:      walk(built + "(", opened + 1, closed)
    if closed < opened: walk(built + ")", opened, closed + 1)

This is pruning, and it is the point#

Nothing invalid is ever built, so nothing has to be checked at the end. Every leaf the walk reaches is an answer.

That is what makes backtracking worth using over generate-then-filter. The condition on each choice cuts off a whole subtree of strings that could never have worked, and the saving compounds with depth.

Where the un-choose went#

There is no explicit undo here, because built is a new string at each call rather than one buffer being shared. Passing a copy is the other way to do backtracking: no undo needed, one copy per node. With short strings that is the clearer trade.

Build it with a shared buffer instead and you will need the undo back, which is worth doing once to feel the difference.

Constraints#

• 1 <= n <= 10