Elegant Recursive Solution for Generating Valid Parentheses


  • 3
    A

    This may not be optimized but it's very easy to understand. The inspiration is here: http://mathforum.org/mathimages/index.php/Catalan_Numbers.

    public static List<String> generateParenthesis(int n) {
        if (n == 0) {
            return Collections.singletonList("");
        }
        if (n == 1) {
            return Collections.singletonList("()");
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<String> A = generateParenthesis(i);
            List<String> B = generateParenthesis(n - 1 - i);
            for (String a : A) {
                for (String b : B) {
                    res.add("(" + a + ")" + b);
                }
            }
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.