Solution: Generate Parentheses

Statement#

For a given number, n, generate all combinations of balanced parentheses.

Constraints:

• $1 \leq$ n $\leq 10$

Solution#

Problems where we require constructing multiple valid answers, such as permutation of any $n$ number or generating a long list of $n$ pairs of balanced parentheses, are good examples to solve using the subsets pattern.

To solve this problem using the subsets pattern, we use a recursive algorithm. The purpose of this algorithm is to correctly generate all of the possible subsets of the parentheses combination.

The key observation in constructing the solution is to keep track of the number of opening, (, and closing, ), parentheses. We’ll use this count to add parentheses in a way that keeps the sequence balanced and valid.

• We only add an opening parenthesis if there is still one to add.

• We only add a closing parenthesis if the number of closing parentheses does not exceed the number of opening parentheses.

The basic algorithm is as follows:​

1. Create a list to store all possible combinations of parentheses.
2. Call the back_track function for n pairs of parentheses, count of left parentheses, count of right parentheses, an empty list for output, and an empty list for the result.
3. If the count of opening and closing parentheses equals n, then we have a valid combination of parentheses, so we will append the string to our list.
4. Otherwise, we will check if the number of opening parentheses is less than n. If yes, we will add opening parentheses to our string and increment the count.
5. Lastly, we will check the count of closing parentheses. If the count is less than the count of opening parentheses, then we will add closing parentheses to our string and increment its count.

Let’s see how this algorithm works for an example, where $n=3$: