See all coding puzzles and patterns here.

Problem Definition

Write a function to print all balanced brace combinations for a given number of braces.

Solution

We construct and maintain a queue of strings to process. And we process this queue completely on every iteration, essentially resulting in a breadth-first traversal of the construction of the strings.

When inspecting each string, we see if it has the required number of open braces. If it does, we append the required number of close braces to balance the string and add it to our result.

If the string is not balanced, we add a new entry to the queue to balance it. In either case, we also update the existing queue entry to add another open brace to it. 

def is_balanced(s, c):
    return c == len(s) / 2

def braces(n):
    if n == 0:
        return []
    # Items of form (string_so_far, open_brace_count)
    queue = [("(", 1)]
    done = []
    while len(queue) > 0:
        to_append = []
        to_remove = []
        for idx in range(len(queue)):
            s, c = queue[idx]
            if c == n:
                done.append(s + ")" * (2*n - len(s)))
                to_remove.append(idx)
                continue
            if not is_balanced(s, c):
                to_append.append((s + ")", c))
            queue[x] = (s + "(", c + 1)
        while len(to_remove) > 0:
            idx = to_remove.pop(len(to_remove) - 1)
            queue.pop(idx)
        queue = queue + to_append
    return done

Complexity

Auxiliary space complexity should be $O(2^n)$ since we must construct at least $2^{n-1}$ strings.

Runtime complexity should be $O(2^n)$ since for every node, starting after (, we are creating 2 branches.