算法:回溯二 生成有效括号对Generate Parentheses
程序员文章站
2024-01-04 11:11:58
...
说明
地址: https://leetcode.com/problems/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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解法
解析:
生成有效括号,满足如下条件
- 左括号个数
left
要大于等于右括号数right
, 也就是必须right>left
才能添加右括号。 - 左右括号剩余数要大于0.
- 回溯退出条件为
if (left == 0 && right == 0)
package backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// https://leetcode.com/problems/generate-parentheses/
public class GenerateParentheses {
public static void main(String[] args) {
GenerateParentheses obj = new GenerateParentheses();
List<String> result = obj.generateParenthesis(3);
System.out.println("result > " + Arrays.toString(result.toArray()));
}
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n <= 0) {
return result;
}
helper(result, "", n, n);
return result;
}
public void helper(List<String> result, String combine, int left, int right) {
//exit
if (left == 0 && right == 0) {
result.add(combine);
return;
}
if (left > 0) {
helper(result, combine + '(', left - 1, right);
}
if (right > left) {
helper(result, combine + ')', left, right - 1);
}
}
}
代码下载
https://github.com/zgpeace/awesome-java-leetcode/blob/master/code/LeetCode/src/backtracking/GenerateParentheses.java