leetcode热题括号生成

数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]

分析：

1.递归过程中变的是填充了多少个左括号和填充了多少个右括号,所以我们要把填充了左括号和右括号的个数作为参数

2.在迭代中我们要保证左括号的个数不能大于n,只要不大于n,就又可以插入左括号或右括号了

3.同时在迭代中要保证右括号的个数不能大于左括号的个数，如果右括号的个数小于左括号的个数，既能插入左括号又能插入右括号

4.结束递归的条件就是右括号的个数 == n

public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); char[] parenthesis = new char[2 * n]; generateParenthesisDfs(0, 0, n, parenthesis, res); return res; } // 目前填充了left个左括号，right个右括号 private void generateParenthesisDfs(int left, int right, int n, char[] parenthesis, List<String> res) { if (right == n) { res.add(new String(parenthesis)); return; } if (left < n) { parenthesis[left + right] = '('; generateParenthesisDfs(left + 1, right, n, parenthesis, res); } if (right < left) { parenthesis[left + right] = ')'; generateParenthesisDfs(left, right + 1, n, parenthesis, res); } }