LeetCode 22. Generate Parentheses
Created at 2018-01-14 Updated at 2018-01-21 Category LeetCode
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:
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.