LeetCode 22. Generate Parentheses
Created at 20180114 Updated at 20180121 Category LeetCode
Question
Given n pairs of parentheses, write a function to generate all combinations of wellformed 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 ‘)’?
 If the remaining numnber of ‘(‘ is greater than 0, add ‘(‘.
 If the number of ‘(‘ added is larger than that of ‘)’, add ‘)’.
 Recursively build a tree.
If you want to calculate the number of outputs, use Catalan Number formula.
Code
CPP code


Python code

