每日一题-括号生成-0721

题目

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

思路

1. 采用深度优先遍历的方式，先把左括号消耗完，再匹配右括号；右括号走到头的时候，开始回溯
2. 当left>right的时候，记得剪枝（因为左括号肯定是先出现的）

代码

public List<String> generateParenthesis(int n) {
    
        List<String> res = new LinkedList<>();
        if(n <= 0)
            return res;
        recur(n, n, new StringBuilder(), res);
        return res;
    }
    private void recur(int left, int right, StringBuilder sb, List<String> res){
    
        if(left == 0 && right == 0){
    
            res.add(sb.toString());
            return;
        }
        // 这个时候要剪枝
        if(left > right)
            return;
        if(left > 0){
    
            sb.append('(');
            recur(left - 1, right, sb, res);
            sb.deleteCharAt(sb.length() - 1); // 回溯
        }
        if(right > 0){
    
            sb.append(')');
            recur(left, right - 1, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }