题目难度：
Medium
题目要求：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]
算法思路：
深度优先遍历+回溯法
1.lc，rc分别表示当前左括号和右括号的个数，只有当lc，rc都等于n时，才满足要求，可以把当前的字符串加入数组中；
2.如果左括号数小于n，就可以再＋“（”；
3.如果右括号数小于n，并小于左括号数，表示括号还不匹配，应该再加上“）”；
4.如此回溯，可以遍历所有的情况，如下图示例所示
代码：
class Solution {
List ans = new ArrayList<>();
public List generateParenthesis(int n) {
dfs(n, 0, 0, "");
return ans;
}
public void dfs(int n, int lc, int rc, String now) {
if (lc == n && rc == n) {
ans.add(now);
} else {
if (lc < n) {
dfs(n, lc + 1, rc, now + "(");
}
if (rc < n && lc > rc) {
dfs(n, lc, rc + 1, now + ")");
}
}
}
}
时间复杂度：
空间复杂度：O（n）
