LeetCode #22. Generate Parentheses プログラミング練習

問題：

難易度:　medium
入力:　正数n
目的: n個の括弧で有効組み合わせをすべて求めよ
出力:　Stringのリスト

前回の♯21で括弧群の有効かどうかを判断しました。
今回は有効な組み合わせをすべて求める問題です。
21問目と違い括弧は”（）”のみなので求めやすくなっています。
括弧が一種類だけなので、有効な条件は左の部分の数と右部分の数が一致している事です。
すべての組み合わせを求めなければいけないので全体探索を使えばいいと思います。

注意すべき事:　

• 組み合わせる途中で左部分が右部分より少ない場合は無効になります。（例: ")))((()))"）

以下回答です。

class Solution {
    public List<String> generateParenthesis(int n) {
        String p = "";
        List<String> result = new ArrayList<String>();
        genP(n, 0, 0, p, result);
        return result;
    }
    public void genP(int n, int left, int right, String p, List<String> result) {
        if (right>left || left>n || right>n) return;
        if (left == n && right == n) {
            result.add(p);
            return;
        }
        genP(n, left+1, right, p+"(", result);
        genP(n, left, right+1, p+")", result);
    }
}

recursiveを使った回答です。
deep first searchで全体探索をし、終了条件は括弧の左部分と右部分が両方ともｎ個の時です。
途中で左部分が右部分より少ない時、又は左部分か右部分がｎより多い時は無効な組み合わせなので破棄します。

今日は以上。
よいプログラミング生活を！