Generate Parentheses Problem

 

The problem is: Given N pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given N = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

The naive solution is to generate all combinations of N pairs of parentheses, then checking if each one is valid.

The naive solution is implemented as follows:

A better solution is to use backtracking. Instead of generation all combinations of N pairs of parentheses, we generate valid parentheses through recursions. This can be done by keeping track of the number of opening and closing brackets.

We can generate an opening bracket if the number of it is less than N. And we can generate a closing bracket if it is less than the number of opening brackets.

The backtracking solution is implemented as follows: