LeetCode题解（2022.2.13）

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);
    }
}