22. Generate Parentheses

题目分析

n 对括号组合，枚举所有可行情况 + 回溯法

代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n == 0) return res;
        helper(res, "", n, n);
        return res;
    }
    /*
    res: 结果集
    paren: 可行解
    left: 剩余的左括号数量
    right: 剩余的右括号数量
    */
    public void helper(List<String> res, String paren, int left, int right) {
        // 判断是否是一个可行解
        // 如果剩余左右括号数量都为 0 了，那么说明找到一个可行解
        if(left == 0 && right == 0) {
            res.add(paren);
            return;
        }
        if(left > 0) {
            
            helper(res, paren + "(", left - 1, right);
        }
        if(right > 0 && left < right) {
            // 每当后面的helper() 函数 return 的时候，并且当前步执行在这里的时候其实也就 return 了
            helper(res, paren + ")", left, right - 1);
        }
    }
}