【Leetcode】22. Generate Parentheses总结
无情
阅读:445
2022-03-12 16:24:44
评论:0
本文章主要介绍了【Leetcode】22. Generate Parentheses,具有不错的的参考价值,希望对您有所帮助,如解说有误或未考虑完全的地方,请您留言指出,谢谢!
回溯法的应用
原题
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
题意是求n组括号的组合方式,要求能够组成合理的左右括号。
分析:
所谓合理的组合方式,应该是左右括号数量相等,在初始情况下应该先添加左括号,在递归过程中左括号数量大于等于右括号的数量,我们记录左右括号的数量和当前字符串,如果左括号数量小于n,则字符串可以添加一个左括号,左括号数量增加一,进入下一轮递归;如果右括号数量小于左括号数量,则字符串添加一个右括号,右括号数量加一后进入下一轮递归。
函数原型:
dfs(String currentString, int leftCount, int rightCount, int n);
迭代的过程如下图所示:
代码:
import java.util.ArrayList;
import java.util.List;
/**
* Author: puyangsky
* Date: 17/4/27
* 方法:递归、回溯
*/
public class L22GenerateParentheses {
private static List<String> list = new ArrayList<>();
public static void dfs(List<String> list, String parenthesis, int left, int right, int count) {
if (parenthesis.length() == count * 2) {//达到最大长度,添加到结果中
list.add(parenthesis);
return;
}
//左括号仍然可以添加的情况
if (left < count)
dfs(list, parenthesis + "(", left + 1, right, count);
//右括号可以添加的情况
if (right < left)
dfs(list, parenthesis + ")", left, right + 1, count);
}
public static List<String> generateParenthesis(int n) {
dfs(list, "", 0, 0, n);
return list;
}
public static void main(String[] args) {
generateParenthesis(3);
for (String l : list) {
System.out.println(l);
}
}
}
结果输出:
((()))
(()())
(())()
()(())
()()()
声明
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。