LeetCode 22. Generate Parentheses
DescriptionExampleCodeConclusion
Description
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Code
java
import java
.util
.LinkedList
;
class Solution {
List
<String> result
;
public void dfs(int n
, int cnt
, String str
) {
if(str
.length() == 2*n
) {
result
.add(str
);
return ;
}
if(cnt
< n
) {
dfs(n
, cnt
+1, str
+"(");
}
if(str
.length() < 2*cnt
) {
dfs(n
, cnt
, str
+")");
}
}
public List
<String> generateParenthesis(int n
) {
result
= new LinkedList<>();
if(n
> 0) dfs(n
, 0, "");
return result
;
}
}
python
class Solution:
def generateParenthesis(self
, n
: int) -> List
[str]:
list = []
def dfs(n
, cnt
, s
):
if len(s
) == 2*n
:
list.append
(s
)
return
if cnt
< n
:
dfs
(n
, cnt
+1, s
+"(")
if len(s
) < 2*cnt
:
dfs
(n
, cnt
, s
+")")
if n
> 0:
dfs
(n
, 0, "")
return list
Others’ Solutionpython
class Solution(object):
def generateParenthesis(self
, n
):
def generate(p
, left
, right
, parens
=[]):
if left
: generate
(p
+ '(', left
-1, right
)
if right
> left
: generate
(p
+ ')', left
, right
-1)
if not right
: parens
+= p
,
return parens
return generate
('', n
, n
)
Conclusion
py的嵌套函数挺好用大佬的py版本写的很简洁
