Printing all valid bracketings

Problem Statement:

Given an integer \(n\), print all valid combinations of brackets “(” and “)”. This means that there is an equal amount of left brackets and right brackets, and at no point in the string are there more right brackets than left brackets. For example, given \(n=2\), you have the two possible bracketings [(()),()()].

I saw this a couple of times as an interview question, and thought it’s worth exploring.

Firstly, I want the list of all possible bracketings stored at returned, not just printed.

We can notice straight away that this problem lends itself to a recursive solution. The answer for \(n=0\) is no bracketings, or the empty string. Otherwise, I found it extremely helpful to write what a valid bracket expression is in Backus-Naur form. It’s as such: \[ \begin{aligned} b &:= \epsilon \\ b &:= \text{'(' } b \text{ ')' } b \end{aligned} \] where \(b\) is a bracket expression and \(\epsilon\) is the empty string. This generates all possible bracketings. This simply means that a valid bracket expression is an empty expression, or a bracket, followed by a valid bracket expression, followed by another bracket, followed by another bracket expression.

We now want to restrict ourselves to bracketings of length \(n\). Again, we can think recursively here. Let \(B(n)\) represent the set of all bracketings of length \(n\) (meaning a total of \(2n\) brackets). Then, \[ \begin{aligned} S(0) &= \{\} \\ S(n) &= \bigcup_{i=0}^{n-1} \text{'('} \times S(i) \times \text{')'} \times S(n-i-1) \end{aligned} \] with a little bit abuse of notation. I mean \(\times\) to represent the Cartesian product that instead of returning tuples, joins strings it one.

We now have to just turn the above into Python code!

def getBrackets(n):
  if(n == 0):
    return [""]

  ret = []

  for i in range(n):

    brackets1 = getBrackets(i)
    brackets2 = getBrackets(n-i-1)

    for b1 in brackets1:
      for b2 in brackets2:
        ret.append( "(" + b1 + ")" + b2)

  return ret

Let’s test it out.

> print(getBrackets(3))
['()()()', '()(())', '(())()', '(()())', '((()))']

which is correct, there are 5 ways.

The above is a perfect example of overlapping subproblems. The code, as it’s executing the for loop, will keep on needing to get the same results for \(getBrackets(i)\), and will have to recompute them every time. We can solve it by keeping a hashmap of previous results for every \(i\).

# Returns a list of all bracketings
bracketDict = dict()

def getBrackets(n):
  if(n == 0):
    return [""]
  if(n in bracketDict):
    return bracketDict[n]

  ret = []

  for i in range(n):

    brackets1 = getBrackets(i)
    brackets2 = getBrackets(n-i-1)

    for b1 in brackets1:
      for b2 in brackets2:
        ret.append( "(" + b1 + ")" + b2)

  bracketDict[n] = ret
  return ret

The above works very well, and in my opinion is much clearer than this second method that I’m about to present (I’ve seen it somewhere online, and a friend of mine claims it’s more clear).

The approach is also recursive, and uses an accumulator which keeps the current string, as well as counters saying how many left brackets we have left and right brackets we have left to use up. When both counters reach 0, we have a valid bracketing and can output it (or store it somewhere). Otherwise, if we can still add “left” brackets, we do so, and in another recursive call, we check if we can put a “right” bracket by checking how many “left” and “right” brackets we currently used up. Here is the code:

def printAllBrackets(n):
  printAllBracketsR("",n,n)

def printAllBracketsR(s,left,right):
  if(left == 0 and right == 0):
    print s
    return
  if(left > 0):
    printAllBracketsR(s+"(",left-1,right)
  if(left < right):
    printAllBracketsR(s+")",left,right-1)

This produces the same valid results as the previous approach, although I find it further away from the generative approach using BNF above.

Hope this was helpful. If you are interested, the number of possible bracketings forms the very well known sequence of Catalan Numbers which is the answer to many other combinatorial problems.