# LeetCode 22. Generate Parentheses

Created at 2018-01-14 Updated at 2018-01-21 Category LeetCode Tag LeetCode

## Question

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:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

## Solution

On LeetCode, the problem is tagged with backtracking tag, however, I think it is more a binary tree problem than a backtracking problem. My idea is we can consider thie problem as a creating a binary tree problem, where at each node ‘(‘ or ‘)’ can be added to the tree. For example when n=3, as the following picture illustrates

So, at what condition can we add ‘(‘ or ‘)’?

1. If the remaining numnber of ‘(‘ is greater than 0, add ‘(‘.
2. If the number of ‘(‘ added is larger than that of ‘)’, add ‘)’.
3. Recursively build a tree.

If you want to calculate the number of outputs, use Catalan Number formula.

CPP code

Python code

## Table of Content

Site by GoingMyWay using Hexo & Random

I am a ML and RL research student

Hide