Balanced parentheses

Why it matters

Brackets appear in almost every programming language. An expression like (a + b) * c only makes sense if each opening bracket has a matching closing bracket in the right place. Compilers check this before they run your code. Editors check it when they colour matching brackets. Calculators and parsers check it when they read a formula.

This lesson asks a related question. Given n pairs of brackets, list every arrangement that is valid. For n = 2 the valid arrangements are (()) and ()(). The arrangement )(() is not valid, because it starts with a closing bracket that has nothing to close.

The method is backtracking again, the same undo habit from the subsets lesson. The new part is the rule that decides which choice is allowed at each step. The search counts how many opening and closing brackets it has placed, and uses those two counts to refuse invalid choices early.

Terms used here

A string is a sequence of characters, such as (()). In C++ it is the std::string type.

A pair is one opening bracket ( and one closing bracket ). We use n pairs, so the finished string has 2 times n characters.

A valid string is one where every closing bracket matches an earlier opening bracket, and every opening bracket is closed by the end. Reading from left to right, the number of opening brackets so far must never be smaller than the number of closing brackets so far, and the two counts must be equal at the end.

A prefix is the part of a string built so far. While the search is running, the prefix is what the function holds in its string variable.

The idea: two counts and two rules

Keep two numbers while you build a string. The number open counts the opening brackets placed so far. The number close counts the closing brackets placed so far. Each step adds one bracket, and the two numbers decide which bracket can come next.

Rule one: you may place an opening bracket while open is less than n. You have only n pairs, so you cannot place more than n openings.

Rule two: you may place a closing bracket while close is less than open. A closing bracket needs an unmatched opening bracket before it. If close already equals open, every opening bracket so far has a partner, so a new closing bracket would have nothing to match.

Think of people walking through a door. Each opening bracket is a person walking in, and each closing bracket is a person walking out. A person cannot walk out before walking in. The two counts are the number of people who have come in and the number who have gone out. The two rules say: someone may come in while fewer than n people have come in, and someone may go out only if more people have come in than have gone out.

The search for n = 2 goes like this. Each line is a prefix and the counts after it.

(             open 1, close 0    rules allow ( and )
((            open 2, close 0    open is now 2 = n, only ) is allowed
(()           open 2, close 1    rules allow )
(())          open 2, close 2    finished, save it
()            open 1, close 1    only ( is allowed
()(           open 2, close 1    open is now 2 = n, only ) is allowed
()()          open 2, close 2    finished, save it

The search finds the two valid strings for n = 2. It never produced )( or )), because the second rule blocked those choices before they grew longer.

The same two counts give the base case. A string is finished when its length is 2 times n, which is the same as saying both counts have reached n.

The first program

The program below builds all valid strings for n from 1 to 4. It also counts how many function calls the search makes, and it compares the result with a brute force method that tries every possible string.

A brute force method checks all possibilities, without any shortcut. For n pairs there are 2 times n positions, and each position is either ( or ). That gives 2 to the power (2 times n) strings. For n = 3 there are 64 of them, and each one is checked from left to right.

Compile it with g++ -std=c++20 -Wall, then run it. The output is:

n=1 count=1 calls=3 brute=1
  ()
n=2 count=2 calls=8 brute=2
  (())
  ()()
n=3 count=5 calls=22 brute=5
  ((()))
  (()())
  (())()
  ()(())
  ()()()
n=4 count=14 calls=64 brute=14
all n=4 strings valid: yes

Read build line by line.

The first if is the base case. When the string has 2 times n characters, the search has placed all its brackets, so it saves a copy and returns. The std::ssize function returns the length as a signed number, which avoids a warning that comparing size() to an int would cause. The mistakes section shows that warning.

The first rule is open < n. If there are still opening brackets left to place, the function adds (, makes the recursive call with open + 1, and then removes the bracket with pop_back.

The second rule is close < open. The function adds ) only when at least one opening bracket is unmatched. It then recurses with close + 1.

The two rules are checked independently, so both branches can run at the same point. For example, with open = 1 and close = 0, both rules apply and the search explores both (( and ().

Now compare the numbers. The count for n = 3 is 5, and the brute force count is also 5. The number of valid strings for n pairs is known as the Catalan number. The numbers 1, 2, 5, 14 are the first four, and the next one is 42, which the exercises check. You do not need that fact to write the search, but it is a useful way to check your output.

The calls column shows how much work the search did. For n = 3 the search makes 22 calls. The brute force method would examine 64 strings, and each one needs up to six checks. The search skips the invalid branches early, so it does not build the rejected strings at all. For n = 4 the gap is larger: the search makes 64 calls, and the brute force tries 256 strings. The gap grows quickly as n grows.

A second example: checking each string

The is_valid function is a useful companion to the search, not a replacement for it. It reads a finished string from left to right and keeps a balance. An opening bracket adds 1 to the balance, and a closing bracket subtracts 1. If the balance ever drops below 0, a closing bracket came before its opening bracket, so the string is invalid. At the end the balance must be 0, because every opening bracket must be closed.

Try it on )(. The first character is ), so the balance becomes -1 at once and the function returns false. Try it on (()()). The balance goes 1, 2, 1, 2, 1, 0, and it never drops below 0, so the function returns true.

The last part of the program checks the search with this function. It runs is_valid on every string the search produces for n = 4, and prints yes only if all 14 are valid. This test does not prove the search finds every valid string. The brute force count matching the search count is the evidence for that, because the brute force method looks at every possible string.

A third example: a harder question about the same search

Suppose you only want the valid strings that begin with ((. The search does not need to build the others. Here is the idea: the first two characters are already known, so the search starts with (( in place and with open = 2 and close = 0. Everything after that is the same search.

The program below does that, and it also counts how many of the n = 3 strings start with (( by filtering the full list. The two numbers should match.

Its output is:

from prefix: 3
  ((()))
  (()())
  (())()
filtered:    3

The first search starts with (( already in the string. It has open = 2 and close = 0, so it adds only what is needed to finish. The second search builds everything and filters. Both give the same three strings, and the first one never builds the strings that begin with ().

Be careful when you start a search from a prefix. The counts must match the prefix. If you start with cur = "((" but pass open = 0, the rules will allow too many opening brackets, and the strings will have more than n of them. The function never checks that the prefix and the counts agree. The caller must keep them in step.

Why two counts are enough

The search does not need to remember which brackets it placed. It only needs the two counts, because the two rules ask only two questions: is there an opening bracket left to place, and is there an unmatched opening bracket to close?

Take n = 2 and look at the prefixes (() and ()(. They are different strings, but each has two opening brackets and one closing bracket. Both have only one choice next: a closing bracket, because open has reached n and the closing rule allows one more ). The next character is the same for both, so the search treats them the same from that point on.

This is why the search stores only numbers and the current string, and why the next example can drop the string altogether.

A fourth example: count without storing strings

The same two rules can count the answers without saving them. The function returns a number instead of filling a list. When both counts reach n, the function returns 1, because one finished string has been reached. Otherwise it adds the answers from its two branches.

The output is:

n=1 count=1
n=2 count=2
n=3 count=5
n=4 count=14
n=5 count=42
n=6 count=132
n=7 count=429
n=8 count=1430
n=9 count=4862
n=10 count=16796

The first four numbers match the earlier program, and the fifth is the 42 from Exercise 1. The function visits the same tree, but it saves nothing. The deepest the call stack can get is 2 times n + 1 calls, the first call plus one for each character. For n = 10 the search counts 16796 valid strings without building a single one of them.

Common mistakes

The most common mistake is writing rule two with the wrong bound. If the check is close < n instead of close < open, a closing bracket can be placed where no opening bracket is waiting. Here is that version, with rule one unchanged, for n = 1:

()
)(
count=2

The string )( is not valid, and the count of 2 is wrong. The fix is to compare close with open, because a closing bracket needs an opening bracket that is still unmatched.

The second mistake is deleting rule two altogether. Then the search never places a closing bracket, so no string reaches full length. Running the same program with rule two deleted and n = 1 prints:

count=0

The search finishes without a single valid string. Rule two is what lets the closing brackets in.

The third mistake is mixing up the counts with the length of the string. The count open is the number of ( characters placed so far, and cur.size() is the total number of characters. Rule one and rule two must use the counts. The length is only used in the base case.

The fourth mistake is a sign comparison warning. The size() function of std::string returns an unsigned number, which cannot be negative. Comparing it to an int in if (cur.size() == 2 * n) produces this warning with -Wall:

warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]

The program in this lesson avoids the warning with std::ssize(cur), which returns a signed number. The (int)cur.size() cast also works, but it is easy to forget in one place.

Practice

Exercise 1

How many valid strings are there for n = 5? Predict the number first from the Catalan sequence in this lesson, then check by changing the program.

Show the answer

The count is 42. Run build(5, 0, 0, cur, out) and print out.size(). The number of function calls for n = 5 is 196.

Exercise 2

Explain why the search never produces ))(( for n = 2.

Show the answer

The search starts with open = 0 and close = 0. Rule two needs close < open, which is false at the start, so the first character cannot be ). The first character must be (. The string ))(( starts with ), so the search never builds it. For n = 2 the search only builds (()) and ()().

Exercise 3

Use the balance check on (()))(. Is it valid? At which character does the balance first drop below 0?

Show the answer

It is not valid. The balances after each character are 1, 2, 1, 0, -1, 0. The balance first drops below 0 at character 5, which is the third ), so the function returns false at that point.

Exercise 4

Change the program so that it prints only the valid strings whose last character is ), for n = 3. How many are there?

Show the answer

Add a filter on the base case: save the string only when cur.back() == ')'. The valid strings for n = 3 all end with ), because a valid string cannot end with an opening bracket. So the count is 5, the same as the full count.

Exercise 5

For n = 3, the search makes 22 calls and the brute force method checks 64 strings. Why is the number of calls smaller than the number of strings?

Show the answer

The search only builds prefixes that can still finish correctly. Rule two blocks any closing bracket that has no opening bracket to match, and rule one stops opening brackets after n are placed. Many of the 64 strings start with a closing bracket or have too many closing brackets, so the search never builds them. The brute force method builds each one in full and only checks it at the end.

Summary

• A valid string of brackets never has more closing brackets than opening brackets at any point, and it ends with equal counts.
• Track two counts, open and close, and use them to decide which bracket can come next.
• The two rules are: place ( while open < n, and place ) while close < open.
• The search cuts off invalid branches as soon as they appear, which keeps the work small.
• Check your output by comparing it with a brute force count for small n, and with the Catalan numbers 1, 2, 5, 14, 42.