Leetcode 括号生成
这个题目是一个经典的 括号生成 问题。题目的要求是给定一个整数 ( n )，代表括号对的数量，生成所有可能的有效括号组合。算法的核心思想是通过 回溯算法 (backtracking) 来构建所有可能的括号组合，并确保它们是有效的。
算法思想：
-
回溯法：回溯算法是一种通过逐步构建解决方案并在发现错误时撤销部分选择的算法。对于这个问题来说，回溯法会通过添加左括号
(和右括号)逐步构建有效的括号组合。 -
决策过程：
- 我们从一个空字符串开始构建，当我们能添加左括号时，优先添加左括号，直到左括号数量达到上限 ( n )。
- 接着，我们只能添加右括号，但右括号的数量不能超过左括号，否则会形成不合法的括号序列（即会出现未匹配的右括号）。
-
终止条件：
- 当生成的字符串长度等于 ( 2 \times n ) 时（因为每对括号需要两个字符，左括号和右括号），说明我们已经生成了一个有效的括号组合，将其加入结果集。
-
详细步骤：
- 从空字符串开始，我们可以在满足一定条件的前提下添加左括号或者右括号。
- 如果当前添加的左括号数目少于 ( n )，则可以继续添加左括号。
- 如果当前添加的右括号数目少于左括号数目（即括号还未完全闭合），则可以添加右括号。
- 通过不断递归添加括号并回溯，最终生成所有可能的有效组合。
代码解释：
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>(); // 用于存放最终结果的列表
backtrack(result, "", 0, 0, n); // 调用回溯函数开始生成括号
return result;
}
private void backtrack(List<String> result, String current, int open, int close, int max) {
if (current.length() == max * 2) { // 如果当前字符串长度达到 2 * n，则说明已经构建了一个有效组合
result.add(current); // 将该组合加入结果列表
return; // 终止当前递归
}
if (open < max) { // 如果左括号数量还没达到 n，则可以添加左括号
backtrack(result, current + "(", open + 1, close, max); // 递归调用，添加左括号
}
if (close < open) { // 如果右括号数量少于左括号，则可以添加右括号
backtrack(result, current + ")", open, close + 1, max); // 递归调用，添加右括号
}
}
具体例子（以 n=3 为例）：
-
从空字符串
""开始，我们可以先添加左括号："("- 继续添加左括号：
"(("- 再添加一个左括号：
"((("- 然后只能添加右括号：
"((()""((())""((()))"（这是一个有效组合）
-
然后我们回溯到之前的状态，再次尝试其他右括号的添加方式，从而生成其它有效组合，如：
"(()())","(())()","()(())","()()()"
通过这种回溯方式，最终可以生成所有 ( n ) 对括号的有效组合。
时间复杂度：
生成 ( n ) 对括号的所有合法组合，其复杂度为 指数级 的。具体时间复杂度大约是 ( O(4^n / \sqrt{n}) )，因为在最坏的情况下，我们需要遍历所有可能的组合，但回溯时剪枝有效减少了不合法的组合。
java solution
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtracking(result, "", 0, 0, n);
return result;
}
private void backtracking(List<String> result, String current, int open, int close, int max) {
if(current.length() == 2 * max) {
result.add(current);
return;
}
if(open < max) {
backtracking(result, current + "(", open + 1, close, max);
}
if(close < open) {
backtracking(result, current + ")", open, close + 1, max);
}
}
}