Balanced Bracket Strings
Problem
Given a number of pairs n, return every string of n opening and n closing round brackets that is balanced: reading left to right, the closers seen so far never outnumber the openers seen so far. Return the strings in sorted order, where an opening bracket sorts before a closing one.
Examples
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]Input: n = 1
Output: ["()"]Input: n = 0
Output: [""]
Why: edge case, zero pairs still form one balanced string, the empty oneHints
0 / 3
Generating every arrangement of brackets and filtering out the bad ones works, but most of them go wrong early. Look for the moment a prefix becomes hopeless.
Two counters describe a prefix completely: how many openers and how many closers it has used. Each of the two possible next characters has its own simple condition.
Recurse while building the string. Add an opener whenever fewer than n have been used, and add a closer only when fewer closers than openers have been used. Record the string when its length reaches 2n. Trying the opener first yields sorted order.
Solution
The two counters are the whole state: an opener is legal while any remain, and a closer is legal only when it has an unmatched opener to close. Because an illegal character is never appended, every leaf the recursion reaches is a valid answer, so no work is wasted on dead prefixes. Branching on the opener before the closer produces the strings in sorted order for free. The number of results is the n-th Catalan number, roughly 4 to the n divided by n to the 1.5, and each costs O(n) to build, which bounds the time; the depth is 2n.
def balanced(n):
out = []
def build(path, opened, closed):
if len(path) == 2 * n: # every bracket is placed
out.append("".join(path))
return
if opened < n: # an opener is still available
path.append("("); build(path, opened + 1, closed); path.pop()
if closed < opened: # a closer has something to match
path.append(")"); build(path, opened, closed + 1); path.pop()
build([], 0, 0)
return out
print(balanced(3)) # -> ['((()))', '(()())', '(())()', '()(())', '()()()']
print(balanced(1)) # -> ['()']
print(balanced(0)) # -> ['']
print(len(balanced(5))) # -> 42Stuck on the idea rather than the code? Backtracking covers it.