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

tree

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.

Code

CPP code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
addingPar(result, "", n, n, n);
return result;
}
void addingPar(vector<string> &v, string str, int n, int left, int right){
if ( left==0 && right==0 ) {
v.push_back(str);
return;
}
if ( left > 0 ) { addingPar(v, str+"(", n, left-1, right); }
if ( n-left > n-right ) { addingPar(v, str+")", n, left, right-1); }
}
};

Python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
result = []
self.add_paran(result, '', n, left=n, right=n)
return result
def add_paran(self, result, s_str, n, left, right):
if left == 0 and right == 0:
result.append(s_str)
return
if left > 0:
self.add_paran(result, s_str + '(', n, left - 1, right)
if n-left > n-right:
self.add_paran(result, s_str + ')', n, left, right - 1)

Table of Content

  1. Question
  2. Solution
  3. Code
Site by GoingMyWay using Hexo & Random
备案号: 粤ICP备16087705号-1

I am a ML and RL research student

Hide