Generate Parentheses

Problem: Generate all strings of $n$ pairs of balanced parentheses.

Approach: Track open and close counts. Add '(' if open < n. Add ')' if close < open.

function backtrack(n, open, close, current, result):
    if current.length == 2 * n:
        result.add(current)
        return
    if open < n:
        backtrack(n, open + 1, close, current + "(", result)
    if close < open:
        backtrack(n, open, close + 1, current + ")", result)

Count: Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$.