[Likou] 22. Bracket generation

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的括号组合.
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]

提示：
1 <= n <= 8

深度优先遍历：树形结构图

分析：

1. 当前左右括号都有大于 0 个可以使用的时候,才产生分支;
2. 产生左分支的时候,只看当前是否还有左括号可以使用;
3. 产生右分支的时候,还受到左分支的限制,右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候,才可以产生分支;
4. 在左边和右边剩余的括号数都等于 0 的时候结算.

代码：

class Solution {
    
 	// 做减法
    public List<String> generateParenthesis(int n) {
    
        List<String> list= new ArrayList<>();
        // 执行深度优先遍历,搜索可能的结果
        dfs("", n, n, list);
        return list;
    }
    /** * @param str 当前递归得到的结果 * @param left 左括号还有几个可以使用 * @param right 右括号还有几个可以使用 * @param list 结果集 */
    private void dfs(String str, int left, int right, List<String> list) {
    
        // 在递归终止的时候,直接把它添加到结果集即可
        if (left == 0 && right == 0) {
    
            list.add(str);
            return;
        }
        // 剪枝（左括号可以使用的个数严格大于右括号可以使用的个数,剪枝）
        if (left > right) {
    
            return;
        }
        if (left > 0) {
    
            dfs(str+ "(", left - 1, right, list);
        }
        if (right > 0) {
    
            dfs(str + ")", left, right - 1, list);
        }
    }
}