22. Generate Parentheses - Medium

前往題目

想法

• 一樣想說要用stack，但是如何使用想不出來

思路

1. 使用backtracking，才能得到所有組合
2. 每次backtrack都檢查(的數量是否小於n，是的話就加上
3. 只有當)的數量小於(的時候才加上)
4. 當)和(的數量等於n的時候才加入到結果裡

backtracking依然很難在腦袋裡運轉…

Code

使用stack的寫法

class Solution {
    List<String> res;
    StringBuilder s;
    int n;
    
    public List<String> generateParenthesis(int n) {
        res = new ArrayList();
        s = new StringBuilder("");
        this.n = n;
        backtracking(0, 0);
        return res;
    }

    private void backtracking(int closeN, int openN) {
        // Used all the parentheses
        if (closeN == n && openN == n) {
            res.add(s.toString());
            return;
        }

        // Can still add open parentheses
        if (openN < n) {
            s.append("(");
            backtracking(closeN, openN + 1);
            s.deleteCharAt(s.length() - 1);
        }
        
        // When close is smaller than open parentheses
        // add close parentheses
        if (closeN < openN) {
            s.append(")");
            backtracking(closeN + 1, openN);
            // Pop for next backtracking
            s.deleteCharAt(s.length() - 1);
        }
    }
}

2024/05/04

• 想到了backtrack，沒看出if條件