2020.12.9每日複習

22.括号生成

分析

• 目前左右括号都有大于 0 個可以使用的時候，才産生分支；
• 産生左分支的時候，隻看目前是否還有左括号可以使用；
• 産生右分支的時候，還受到左分支的限制，右邊剩餘可以使用的括号數量一定得在嚴格大于左邊剩餘的數量的時候，才可以産生分支；
• 在左邊和右邊剩餘的括号數都等于 0 的時候結算。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n == 0) return res;
        dfs("", n, n, res);
        return res;
    }
    //left表示左括号還剩幾個，right表示右括号還剩幾個，str表示拼接的括号字元串
    public void dfs(String str, int left, int right, List<String> res) {
        if(left == 0 && right == 0) {  //如果左右同時為0，則全部周遊完成
            res.add(str);
            return;
        }
        if(left > right) { //如果左括号剩下的比右括号多，則不可能是有效的括号組合
            return;
        }
        if(left > 0) {
            dfs(str + "(", left - 1, right, res);
        }
        if(right > 0) {
            dfs(str + ")", left, right - 1, res);
        }
    }
}