Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example
given n = 3, a solution set is:
1
2
3
4
5
6
7
| [
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
|
Solution
- l: len of left parenthese you need to fill
- r: len of right parenthese you need to fill
r should be always >= l
Java:
(Generate-Parentheses.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution {
public List<String> generateParenthesis(int n) {
List<String> ret = new LinkedList<String>();
dfs(ret,"",0,0,n);
return ret;
}
public void dfs(List<String> ret, String tmp, int l, int r, int max){
if(tmp.length() == 2*max){
ret.add(tmp);
return;
}
if(l<max)
dfs(ret, tmp+'(', l+1, r, max);
if(r<l)
dfs(ret, tmp+')', l, r+1, max);
}
}
|
(Generate-Parentheses.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution(object):
def getParenthesis(self, l, r, tmp, ret):
# 有括号比左括号多
if r < l:
return
if l ==0 and r == 0:
ret.append(tmp)
if l > 0:
self.getParenthesis(l-1,r,tmp+'(',ret)
if r > 0:
self.getParenthesis(l,r-1,tmp+')',ret)
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
ret = []
if n == 0:
return ret
self.getParenthesis(n,n,"",ret)
return ret
|