22 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
所有可能的情况为一颗高度为n的满二叉树，因此可以深度优先遍历，同时配合适当的剪枝策略。由于需要保证左括号数量大于右括号，且小于等于n，选择right和left两个变量表示左右括号个数。
算法：
class Solution { List result = new ArrayList(); public List generateParenthesis(int n) { if (n <= 0) return null; dfs("", 0, 0, n); return result; } public void dfs(String paths, int left, int right, int n){ //深度优先遍历 if (left > n || right > left) //左括号个数小于等于n且左括号大于等于右括号个数 return; if (paths.length() == n * 2){ //括号总个数等于2*n则加入结果列表 result.add(paths); return; } dfs(paths + "(", left + 1, right, n); dfs(paths + ")", left, right + 1, n); }}