Typical Code Interview Problem 3: Generating All Possible Combinations of Well-Formed Brackets

Question:

Given a number n, generate all possible combinations of n well-formed brackets. Here are some examples and some starting code. def generate_brackets(n):

#Fill this in. print(generate_brackets(1))

# [‘()’] print(generate_brackets(3))

# [‘((()))’, ‘(()())’, ‘()(())’, ‘()()()’, ‘(())()’]

Response from ChatGPT

To generate all possible combinations of n well-formed brackets, we can use a recursive approach.

The idea is to add opening brackets until we reach half of n, then we start adding closing brackets. We keep track of the number of opening and closing brackets added and add closing brackets only when the number of opening brackets is greater than the number of closing brackets.

Here’s the implementation of generate_brackets() function:

def generate_brackets(n):
    result = []
    generate_helper(n, '', 0, 0, result)
    return result
    
def generate_helper(n, current, open_count, close_count, result):
    if len(current) == n * 2:
        result.append(current)
        return
    if open_count < n:
        generate_helper(n, current+'(', open_count+1, close_count, result)
    if close_count < open_count:
        generate_helper(n, current+')', open_count, close_count+1, result)

In generate_helper(), we check if we have reached the length of n*2 (since each well-formed bracket contains 2 characters, either an opening or closing bracket). If we have reached the length, we add the current string to the result list.

If the number of opening brackets added is less than n, we call generate_helper() recursively with the updated string, open count incremented by 1, and the same close count.

If the number of closing brackets added is less than the number of opening brackets, we call generate_helper() recursively with the updated string, open count unchanged, and the close count incremented by 1.

Finally, we return the result list. Here’s how we can use this function:

print(generate_brackets(1))
# ['()']

print(generate_brackets(3))
# ['((()))', '(()())', '()(())', '()()()', '(())()']

If you don’t want to use recursion, you can use an iterative approach to generate all possible combinations of n well-formed brackets using a stack.

The idea is to keep track of the number of opening and closing brackets we have added so far. We push an opening bracket onto the stack until we have added n opening brackets. For each opening bracket, we also keep track of the number of closing brackets we need to add to make it a well-formed bracket.

Then we start popping the stack until it is empty. For each popped bracket, we decrement the number of closing brackets needed for the previous bracket. If the number of closing brackets needed for the previous bracket is greater than 0, we push a closing bracket onto the stack. We continue this process until the stack is empty.

Here’s the implementation of generate_brackets() function using an iterative approach:

def generate_brackets(n):
    if n == 0:
        return []
    result = []
    stack = [(0, 0, '')] # (opening_count, closing_count, string)
    while stack:
        opening_count, closing_count, current = stack.pop()
        if opening_count == n and closing_count == n:
            result.append(current)
        else:
            if opening_count < n:
                stack.append((opening_count+1, closing_count, current+'('))
            if closing_count < opening_count:
                stack.append((opening_count, closing_count+1, current+')'))
    return result

In the above code, we first handle the case where n is 0, and return an empty list. Otherwise, we initialize an empty result list and a stack with a tuple containing the initial values of opening_count, closing_count, and current string.

We then enter a loop that continues until the stack is empty. In each iteration, we pop a tuple from the stack and check if we have added n opening and closing brackets. If we have, we append the current string to the result list.

If we haven’t added n opening brackets yet, we push an opening bracket onto the stack with updated opening_count and current string. Similarly, if we haven’t added n closing brackets yet and the number of closing brackets is less than the number of opening brackets, we push a closing bracket onto the stack with updated closing_count and current string.