Generate Parentheses

此題就是考 DFS，我一開始也忘記怎麼做

但記住遞迴三要件

• 每次要做的事
• 結束條件
• 去掉上回合

我從「結束條件」有想到是左括號有三個時和右括號有三個時就回傳，

從這裡又想到那麼參數需要 leftCount, rightCount

從這裡想到要做的事也跟這兩個參數有關係吧？

當 leftCount < n 時，我們就可以放入左括號，然後進行遞迴

到這邊我就卡住了，因為我會以為馬上就要放入右括號，再進行遞迴，那這樣就永遠只會有 ()() ... 這種

可是我又怕我我回不到一開始只放入一個 ( 的狀態，

後來發現在遞迴完就去掉，再放入右括號，就可以產生 () 開頭的結果，因為 ((( , (( 在之前的左括號遞迴就做過了，

還有一點要注意，如果沒有左括號時是不能有右括號的，因此要 rightCount < leftCount

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    if (n <= 0) {
        return result;
    }

    List<String> current = new ArrayList<>();
    helper(result, current, 0, 0, n);
    return result;
}

private void helper(List<String> result, List<String> current, int leftCount, int rightCount, int n) {
    if (leftCount == n && rightCount == n) {
        StringBuilder sb = new StringBuilder();
        for (String s : current) 
            sb.append(s);
        result.add(sb.toString());
        return;
    }

    if (leftCount < n) {
        current.add("(");
        helper(result, current, leftCount+1, rightCount, n);
        current.remove(current.size() - 1);
    }
    if (rightCount < leftCount) {
        current.add(")");
        helper(result, current, leftCount, rightCount+1, n);
        current.remove(current.size() - 1);
    }
}