一.题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
二.示例
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1
输出：["()"]三.提示：
1 <= n <= 8
四.解法:
方法一：DFS + 剪枝
题目中 n 的范围为 [1,8]，因此我们直接通过“暴力搜索 + 剪枝”的方式通过本题。
我们设计一个函数 dfs(l,r,t)，其中 l 和 r 分别表示左括号和右括号的数量，而 t 表示当前的括号序列。那么我们可以得到如下的递归结构：
- 如果 l>n 或者 r>n 或者 l<r，那么当前括号组合 t 不合法，直接返回；
- 如果 l=n 且 r=n，那么当前括号组合 t 合法，将其加入答案数组
ans中，直接返回； - 我们可以选择添加一个左括号，递归执行
dfs(l + 1, r, t + "(")； - 我们也可以选择添加一个右括号，递归执行
dfs(l, r + 1, t + ")")。
时间复杂度 O(2n×2×n)，空间复杂度 O(n)。
五.代码
Java代码
class Solution {// 用于存储结果的列表private List<String> ans = new ArrayList<>();// 存储括号对数private int n;public List<String> generateParenthesis(int n) {// 初始化括号对数this.n = n;// 开始深度优先搜索dfs(0, 0, "");// 返回结果列表return ans;}// 深度优先搜索函数private void dfs(int l, int r, String t) {// 如果左括号或右括号数量超过 n，或者右括号数量超过左括号，返回if (l > n || r > n || l < r) {return;}// 如果左括号和右括号数量都等于 n，添加当前组合到结果列表if (l == n && r == n) {ans.add(t);return;}// 递归添加左括号dfs(l + 1, r, t + "(");// 递归添加右括号dfs(l, r + 1, t + ")");}
}注释说明·结果列表：ans 用于存储所有可能的有效括号组合。·括号对数：n 表示需要生成的括号对数。·generateParenthesis 方法：初始化括号对数并调用 dfs 函数开始生成括号组合。·dfs 函数：递归生成括号组合。·边界条件：如果左括号或右括号数量超过 n，或者右括号数量超过左括号，直接返回。·终止条件：如果左括号和右括号数量都等于 n，将当前组合添加到结果列表。·递归调用：分别尝试添加左括号和右括号，继续递归生成组合。
