Daily bit(e) of C++ | Valid parentheses sequences
Daily bit(e) of C++ #182, Common interview problem: Valid parentheses sequences
Today we will look at a common C++ interview problem: Valid parentheses sequences.
Given n pairs of parentheses, generate all valid combinations of these parentheses.
For example, for n==3 all valid combinations are: ()()(), (()()), ((())), (())() and ()(()).
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/eYWeMEhTr.
Solution
Enumerating all possible combinations under a specific constraint is a canonical problem for backtracking.
Backtracking explores the solution space in depth-first order while ensuring the path/partial solution maintains all imposed constraints.
For our problem of generating valid combinations of parentheses, each step during our exploration is either adding a left or right parenthesis. To maintain the constraint of validity, we need to follow the following rules:
We only have n left parenthesis; therefore, we can only add one if we haven’t used n.
A right parenthesis must always match some preceding left parenthesis; therefore, we can only add a right parenthesis if the number of left parentheses exceeds the number of right parentheses.
Finally, to avoid re-counting the number of left and right parentheses we have already used, we keep track of these numbers as we recurse towards the solution.
