Balanced parentheses in Python

Why this matters

Brackets appear all through code. A maths expression such as (2 + 3) * (4 - 1) needs its brackets to match. A program with { and } needs every opening brace to have a closing brace in the right place. Compilers and text editors check this all the time. A related question is harder: given a number n, list every correct way to arrange n pairs of brackets. This is the question this lesson answers.

The method is the same backtracking pattern you have already seen in the subsets and k-subsets lessons. You build a string one character at a time, you try each allowed next character, you explore, and you undo the choice when the branch is done. The new part is the rule for what counts as allowed. That rule is written as two counters, and it lets you stop bad branches early.

Words used in this lesson

A bracket pair is one opening bracket and one closing bracket that belong together. Here the brackets are round, ( and ). A valid string of n pairs has exactly n opening brackets and n closing brackets, and every prefix of it (the first part of the string, from the start up to any point) has at least as many opening brackets as closing brackets. A prefix is any beginning part of a string. A counter is a number that goes up or down as you work, such as the number of opening brackets used so far.

Pruning means cutting off a branch of the search tree because no valid answer can grow from it. The term comes from cutting a tree's branches. A recursion tree is the picture of each call as a point and each choice as a line down to the next call. You have met it in the recursion trees lesson.

Start with a plain example

Take two pairs of brackets, so n equals 2. There are four brackets in total: two opening and two closing. Before writing any code, try to arrange them by hand.

You can write (()). Read it from left to right. The first character is an opening bracket, so you are at depth 1. The second is another opening bracket, so the depth is 2. The third is a closing bracket, so the depth is 1. The fourth is a closing bracket, so the depth is 0. The string is valid, because the depth never went below 0 and it ends at 0.

You can also write ()(). Here the depth goes 1, 0, 1, 0. It never goes below 0, and it ends at 0. That is valid too.

Now try )(. The first character is a closing bracket, so the depth would be negative straight away. There is no opening bracket that the first closing bracket could match. The string is not valid, and no valid string can begin with a closing bracket. So the answer for n equals 2 is two strings: (()) and ()().

This hand method uses one idea, the depth. The depth is the number of opening brackets not yet closed. Each opening bracket adds one. Each closing bracket takes one away. A string is valid when the depth never goes negative and it is back at zero at the end. The code uses two counters instead of one depth, because it needs to know how many opening brackets have been placed in total and how many closing brackets have been placed in total. The two counters together tell you the depth: depth equals open minus close.

The two rules

The code follows two rules, and each rule is a check made before a character is added.

Rule 1. You may add an opening bracket only when open is less than n. That is, you have not used all n opening brackets yet.

Rule 2. You may add a closing bracket only when close is less than open. That is, there is an opening bracket still waiting for its match. A closing bracket added when close equals open would make the depth negative.

These two rules are the whole idea. The search begins with an empty string, and at each step it tries the rules in order. When neither rule allows a character, the branch ends. When the string reaches length 2 times n, the string is complete and is saved.

The rules also guarantee that the output has no invalid strings at all. You never need to check a finished string. Each one was valid at every step.

Example 1: the search written in code

Here is the code that does this. The function is called build. It takes five inputs: the number n, the counters open_count and close, a list of characters called current that holds the string being built, and a list called result that holds the finished strings. The name open_count avoids a clash with Python's built-in open function.

The string is built as a list of single characters. A list can grow and shrink at the end with append and pop. When the string is complete, "".join(current) makes a new string with the same characters. A Python string cannot be changed once it is made, so the saved string stays the same even after the list changes again.

The calls counter at the top of the file is only there to show how much work the search does. It goes up by one each time build starts, and global calls lets build change it. It is not needed for the answer.

Press Run. The output is:

n=1 count=1 calls=3
n=2 count=2 calls=8
n=3 count=5 calls=22
n=4 count=14 calls=64
n=5 count=42 calls=196
['((()))', '(()())', '(())()', '()(())', '()()()']

Trace the n equals 2 case by hand to see the calls. The first call has an empty string, with open_count equal to 0 and close equal to 0. Rule 1 allows an opening bracket, so the call adds ( and calls again with open_count equal to 1. That call can add another (, reaching ((, and then the next call is at length 2, which is not 4, and it can add a ). The search keeps going this way and reaches (()) as the first saved string. Back up the tree, the search tries the other branches and saves ()() as the second string.

The output for n equals 2 has the two strings we found by hand. For n equals 3 it has five, and the list shows the order the search found them. The strings always begin with (, because Rule 2 blocks any closing bracket when close equals open_count equals 0. The search finds the strings in an order that reads like a dictionary, with ( coming before ).

Example 2: the number of strings grows by a known pattern

The counts in the output are 1, 2, 5, 14 and 42. These are called the Catalan numbers. A Catalan number counts many different objects, and valid bracket strings are one of them. You do not need the formula to use this method. But it helps to know that the count will not grow as fast as the number of all possible strings, which you will see in Example 3.

The number of calls grows too, but more slowly than the total number of arrangements of brackets. For n equals 3 the search makes 22 calls and saves 5 strings. The calls are the work the search does, and each call adds one character or finishes a string. Every call is part of a path to a valid string or to a dead end that Rule 1 or Rule 2 blocked.

A dead end is a branch that cannot finish. For example, if the current string is (())), its depth went negative at the fifth character. Rule 2 stops that at the moment it would happen, so the search never builds such a string at all.

Example 3: generate all strings and then filter

To see why the two rules matter, try the simpler method. You can list every string made of six characters, each either ( or ), and then keep only the valid ones. This method does not use any rule while building. It builds every string and checks at the end. The tried counter is a one-item list, so the function can change it.

The output is:

tried = 64 valid = 5
['((()))', '(()())', '(())()', '()(())', '()()()']

The two methods find the same five strings. The difference is the work. The filter method builds and checks 64 strings, because there are two choices for each of six positions, and 2 to the power 6 is 64. The rule method made 22 calls for the same answer. For a larger n the gap grows very fast. The filter method needs 2 to the power of 2n strings, and the rule method only visits the branches that can still finish.

This is what pruning means. The rule method never walks into a branch it knows is dead, so it does not spend time on it.

Tracing the search for n equals 2

The search is easier to follow as a tree. Each line below is one call of build. The text in quotes is the string at that point, and open_count and close are the counters. The lines starting with add show the character that was tried.

build(open_count=0, close=0) ""
  add ( -> build(open_count=1, close=0) "("
    add ( -> build(open_count=2, close=0) "(("
      open_count is 2, so no more opening brackets
      add ) -> build(open_count=2, close=1) "(()"
        add ) -> build(open_count=2, close=2) "(())"  length is 4, saved
    add ) -> build(open_count=1, close=1) "()"
      add ( -> build(open_count=2, close=1) "()("
        add ) -> build(open_count=2, close=2) "()()"  length is 4, saved
      add ) is not allowed, because close (1) is not less than open_count (1)
  add ) is not allowed, because close (0) is not less than open_count (0)

The tree has two leaves that are saved strings, (()) and ()(). Every other branch stops because a rule blocked the next character. The last line of the tree is the pruning step in action. The search never builds ) at the start, so it never builds a string that starts with a closing bracket.

Notice that the tree shows the count of 2 without any checking at the end. Each leaf is valid because of the rules it passed on the way down.

How to check your code

The number of valid strings for n pairs is a known sequence, which is 1, 2, 5, 14, 42, and so on. A function for this problem should print these counts for n equal to 1, 2, 3, 4 and 5. If it prints a different count, the rules are wrong.

Also check the strings themselves. Every saved string should have exactly 2 times n characters, the same number of ( and ), and a depth that never goes negative when you read it left to right. You can check the depth by hand for a short string, such as (()() which fails because it ends at depth 1.

Cost in plain numbers

The table compares the two methods. The first column is n, the number of pairs. The second is the number of valid strings. The third is the number of calls the rule-based search made, from the run in Example 1. The fourth is the number of complete strings the filter method builds, which is 2 to the power of 2 times n.

The filter column is a formula, and the value for n equal to 3 (64) is the one measured in Example 3. The calls grow by a factor of about three each time n goes up by one, while the filter's count grows by a factor of four. For n equal to 10 the filter would build 2 to the power of 20, which is more than a million strings, and the rule-based search still follows only the branches that can finish.

Common mistakes

Each mistake below is easy to make. The outputs shown are the real outputs of small programs that contain the mistake.

Mistake 1: using <= instead of < in Rule 2

If Rule 2 reads close <= open_count, the code allows a closing bracket when no opening bracket is waiting. The search then builds strings that start with ). With n equals 2 the output is:

['(())', '()()', '())(', ')(()', ')()(']

Three of the five strings are not valid. The strings ())(, )(() and )()( have a depth that goes negative. The fix is to use <, so that a closing bracket needs an opening bracket waiting for it.

Mistake 2: stopping at length n instead of 2 times n

The string must hold n pairs, which is 2 times n characters. If the base case checks len(current) == n, the search stops after n characters. For n equals 3 the output is:

['(((', '(()', '()(']

Each of those strings has 3 characters, which is not enough for 3 pairs, and ()( is not balanced. The fix is to compare with 2 * n.

Mistake 3: saving the list instead of a string

The result list holds strings. The current list holds single characters, and it keeps changing while the search runs. If you write result.append(current) in place of result.append("".join(current)), Python does not complain. It stores a reference to the same list every time, and that list is empty when the search ends. For n equals 2 the output is:

[[], []]

Two entries are printed, and both are empty lists. Python did not raise an error, so this bug is quiet. The fix is to join the characters into a string at the moment the string is complete. A copy with current[:] would also work for a list, but a string is the value the problem asks for.

Mistake 4: forgetting to undo the last character

Without the two undo lines current.pop(), the list keeps the characters from the branch that was just finished. The next branch then starts from the wrong list. With n equals 2 the program prints only one string:

['(())']

The second valid string ()() is never found, because the state was polluted by the first branch. The undo step is what makes each branch start from the same list that the parent call had.

Practice

Exercise 1 (easy). List every valid string for n equals 1, and every valid string for n equals 2. Check each one by reading it from left to right and keeping the depth.

Show the answer

For n equals 1 the only valid string is (). For n equals 2 there are two, (()) and ()(). In each case the depth never goes negative and ends at 0.

Exercise 2 (easy). Is )( a valid string? Explain which rule stops the search from ever building it.

Show the answer

No. The first character is a closing bracket, and no opening bracket is waiting for it, so close (0) is not less than open_count (0). Rule 2 blocks it, so the search never starts a string with ).

Exercise 3 (medium). Change the build(3, ...) call in the program to build(0, ...) and run the code. What does it print, and why?

Show the answer

The output is ['']. The list holds one item, the empty string, and Python shows an empty string as two quote marks with nothing between them. Rule 1 needs open_count less than 0, which is false, and Rule 2 needs close less than open_count, which is 0 less than 0, also false. The base case is reached straight away, because the length 0 equals 2 times 0, so the empty string is saved. The count is 1, which matches the Catalan number for n equals 0.

Exercise 4 (medium). Change the generate-and-filter program in Example 3 so that it builds strings of length 4 instead of 6. Predict the numbers before you run it.

Show the answer

There are two choices for each of four positions, so 2 to the power 4 is 16. The program prints tried = 16 valid = 2, and the two valid strings are (()) and ()().

Exercise 5 (harder). Starting from the code in Example 1, change Rule 1 so that the search allows at most n minus 1 opening brackets. Predict whether the output for n equals 2 changes. Then run it and explain the output in one or two sentences.

Show the answer

The output changes. With n equals 2, Rule 1 now allows only one opening bracket, so the search can add ( once and then ) once, reaching (), and then it is stuck with length 2 and no bracket it may add. The line for n equals 2 in the output reads n=2 count=0. The reason is that a valid string of n pairs needs n opening brackets, so limiting them to n minus 1 removes every answer.

Summary

• A valid string of n pairs has n opening and n closing brackets, and its depth never goes negative.
• Two counters, open_count and close, tell you which next characters are allowed: an opening bracket while open_count is less than n, and a closing bracket while close is less than open_count.
• Backtracking builds the string one character at a time, and the undo step removes the last character before the next choice.
• The rules prune branches that cannot finish, so the search does far less work than building every string and filtering at the end.
• Join the characters into a string with "".join when the string is complete, because the list keeps changing after that.