括号生成

回溯

中等#22Java时间 O(n·Cₙ)，Cₙ 为第 n 个卡特兰数空间 O(n)，不计结果

题目要做什么

生成由 n 对括号组成的所有合法括号串。任意前缀中的右括号数量都不能超过左括号数量。

题目示例输入n = 3

题目示例输出["((()))","(()())","(())()","()(())","()()()"]

01 为什么这样做

左括号还没用满就可追加左括号；右括号比左括号少才可追加右括号。直接限制合法前缀，避免先生成所有字符串再筛选。

始终成立的条件

0 ≤ right ≤ left ≤ n，路径始终是某个合法结果的前缀。

02 看见算法执行

动画与代码同步

修改输入，播放自己的例子

当前使用题目示例

演示输入 · JSON

预期输出 · 可选

修改输入会改变执行过程；预期输出用于核对结果。

数组 / nums步骤 1

执行状态

本次演示输出播放到最后查看

Solution.java参考解法

1class Solution {2    public List<String> generateParenthesis(int n) {3        List<String> result = new ArrayList<>();4        search(n, 0, 0, new StringBuilder(), result);5        return result;6    }7    private void search(int n, int left, int right, StringBuilder path, List<String> result) {8        if (path.length() == 2 * n) {9            result.add(path.toString());10            return;11        }12        if (left < n) {13            path.append('(');14            search(n, left + 1, right, path, result);15            path.deleteCharAt(path.length() - 1);16        }17        if (right < left) {18            path.append(')');19            search(n, left, right + 1, path, result);20            path.deleteCharAt(path.length() - 1);21        }22    }23}

键盘控制：A 后退 · D 前进

括号生成

题目要做什么

这道题的完整课程将在正式实现中补齐

01 为什么这样做

02 看见算法执行

修改输入，播放自己的例子

编程练习

Java 编程练习