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:


Penji Team

December 27th

View Profile

Get in Touch

Thanks! We'll reach out shortly.

Rate this post

You won't be taken from this page or asked to login

Thanks! We'll reach out shortly.