Focus on the recursion – part II

In a previous post, we talked about how recursion works, and what are the steps to implement it. In this post, we will focus on a very beautiful question, which is apparently asked at Google programming interviews: generate all balanced bracket combinations

The question is as follow:
your goal is to print all possible balanced brackets combinations up to N. For example:
for N = 2: [“( )( )”, “( ( ) )”]
for N = 3: [“( )( )( )”, “( ( ( ) ) )”, “( ( )( ) )”, “( )( ( ) )”, “( ( ) )( )”]
etc…

For this classic question, the best flow i could find, is to visualize all of the action field at each step as a binary tree.
Explanation: if you tried to write down one of the possible combinations, for every brackets you add, you have the choice between an opening brackets, or a closing brackets. Nothing else.
But the question is: what is the decision rule ?
First of all, you can always add an opening brackets as long as you still have one which was not placed yet. No matter what is my string situation, an opening brackets can be added. But a closing can be added if and only if you already placed more opening than closing (remember the results needs to be balanced, to each closing should correspond an opening). In other words, you have more closing brackets left to place than opening ones.

Let’s visualize with an example, for N=3:
Let’s call number of remaining opening O, and C for closings. At first, we have O = C =3.
I must start with an opening: “(“. Now C = 3, O = 2.
Then I have 2 choices:
1. opening again: “( (“.Now C = 3, O = 1
2. because C > O, I can close: ” ( )”. Now C = 2, O = 2.

From each new case, we can deduct new cases, according to the 2 rules mentioned above:
1. Or adding an opening if O > 0.
2. Or adding a closing if C > 0 and C > O.
We stop when there are no more brackets left to place.

It means we need to keep trace of remaining brackets, and define a global string array for adding new found combinations to it.

Now let’s see the code (here in python, but this can obviously any language), and explain it part by part:

#!/usr/bin/env pytho#!/usr/bin/env python

import sys

result = []
 
def displayAllBracketsBalancedCombinations(N):
    """
    :param N: number of brackets to place 
    """
    findAllCombinationsCore(N, N)
    print (result)
    print ("number of results: {}".format(len(result)))


def findAllCombinationsCore(left, right, current_str = ""):
    """
    This is the recursive function
    :param left: remaining opening brackets
    :param right: remaining closing brackets
    :param current_str: current result string
    :return: 
    """
    current_str_arg = current_str
    if left == 0 and right == 0:
        result.append(current_str)
        return
    if left > 0:
        current_str += '('
        findAllCombinationsCore(left - 1, right, current_str)
    if right > 0 and right > left:
        current_str_copy += ')'
        findAllCombinationsCore(left, right - 1, current_str_copy)
        
displayAllBracketsBalancedCombinations(int(sys.argv[1]))

There are 2 functions here: the main function – displayAllBracketsBalancedCombinations – which simply calls the core function – findAllCombinationsCore.

displayAllBracketsBalancedCombinations gets N as argument, which is the number of pair of brackets we want to build combinations from.
It will call the core function, the one which is doing the real job, findAllCombinationsCore.

findAllCombinationsCore gets several arguments:

  • left: counter for remaining left brackets
  • right: counter for remaining right brackets
  • current_str: as the recursion progresses, brackets are added to this string, which is passed to next recursion level, and finally added to the result array
def findAllCombinationsCore(left, right, current_str = ""):

findAllCombinationsCore prototype, with default argument for current_str (empty string)

    if left == 0 and right == 0:

This is our stop condition, no more brackets (left or right) are left

        result.append(current_str)
        return

In this case, we are done with this string, and simply add it to the result array.

Now we are dealing with the 2 cases we mentioned above:

    if left > 0:
        current_str += '('
        findAllCombinationsCore(left - 1, right, current_str)

First possibility, as we said, we have at least one opening bracket left, just add it to the current string.
At this step, it is like the function says: “Ok!! I have done my job, now let’s delegate the next step to….new call to the same function”. This is so damn cool!!!
Of course, when passing the baton to next call, you need to make sure arguments are updated. That means: remaining opening brackets are one less, and depth is one more.

    if right > 0 and right > left:
        current_str_copy += ')'
        findAllCombinationsCore(left, right - 1, current_str_copy)

This part is the one where we decide to add right bracket, when the conditions are, as we mentioned above:

  1. right brackets counter is still positive
  2. we have more (and not equal to) right brackets than left ones, which means that by adding it, we are actually closing some previously opened bracket.

If both conditions are filled, we enter the if statement, and add a closing bracket to the string, then call the core function again with updated arguments, as mentioned before.

A little but important remark, you may have noticed that the second if conditions, is working with a copy of the input string, and not on the same one.
This is simply due to the fact the recursive calls modify the current_str variable, and when coming back to it, it is not the same as it was when entering the function. So we save a copy and use it for the next if.

That’s all!! We made it.
I really enjoyed writing this post, as it forced me to improve my original code, and made me understand the algorithm a lot better. I can only recommend you to sit on that, and write it by yourself, if not already done.
Of course, I would be pleased to get any comments, positive or not, as long as they are constructive ones!

Thanks for reading, and see you soon for next post!

One comment

Leave a Reply to Pablo F. Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s