Get in Touch

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:


Eunsub Lee

January 12, 2020

View Profile

Get in Touch

About Penji

Content

support@penjiapp.com

1719 Emerson St

Denver, CO, 80218