package com.ljp.test.leetcode;
import java.util.ArrayList;
import java.util.List;
/**
* <h2>22. 括号生成
*
* 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
*
*
* 示例 1：
*
* 输入：n = 3
* 输出：["((()))","(()())","(())()","()(())","()()()"]
* 示例 2：
*
* 输入：n = 1
* 输出：["()"]
*
* 提示：
*
* 1 <= n <= 8
*
* 来源：力扣（LeetCode）
* 链接：<a href="https://leetcode.cn/problems/generate-parentheses">22. 括号生成
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class Number0022{
public static void main(String[] args) {
System.out.println(BacktrackAndPruning.generateAllParentheses(1));
System.out.println(BacktrackAndPruning.generateAllParentheses(2));
System.out.println(BacktrackAndPruning.generateAllParentheses(3));
System.out.println(BacktrackAndPruning.generateAllParentheses(4));
System.out.println(BacktrackAndPruning.generateAllParentheses(5));
}
/**
* 使用回溯算法和剪枝算法
*/
private static class BacktrackAndPruning{
public static List<String> generateAllParentheses(int n) {
List<String> allParentheses =new ArrayList<>();
backtrackAndPruning(allParentheses, new StringBuilder(), 0, 0, n);
return allParentheses;
}
/**
* 回溯算法和剪枝算法
*
* @param allParentheses 所有括号集合
* @param parentheses 单个括号（值传递，复制的引用）
* @param open 左括号（值传递）
* @param close 右括号（值传递）
* @param max 最大括号数
*/
private static void backtrackAndPruning(List<String> allParentheses, StringBuilder parentheses, int open, int close, int max) {
// 剪枝算法
if (open > max || open < close) {
return;
}
if (parentheses.length() == max *2) {
allParentheses.add(parentheses.toString());
return;
}
// 回溯算法，左增加
backtrackAndPruning(allParentheses, parentheses.append('('), open +1, close, max);
// 回溯结束之后，StringBuilder置空
parentheses.deleteCharAt(parentheses.length() -1);
// 回溯算法，右增加
backtrackAndPruning(allParentheses, parentheses.append(')'), open, close +1, max);
// 回溯结束之后，StringBuilder置空
parentheses.deleteCharAt(parentheses.length() -1);
}
}
}
网友评论