Generate Parentheses

1package pkg5leetcode.top100;2 3/*4 * Generate Parentheses | LC 225 * APPROACH: Backtrack add '(' or ')' while valid counts.6 * COMPLEXITY: Time O(4^n/sqrt(n)), Space O(n)7 */8import java.util.*;9 10public class top100_LC22GenerateParentheses {11    static List<String> generateParenthesis(int n) {12        List<String> res = new ArrayList<>();13        backtrack(n, 0, 0, new StringBuilder(), res);14        return res;15    }16 17    static void backtrack(int n, int open, int close, StringBuilder sb, List<String> res) {18        if (sb.length() == 2 * n) { res.add(sb.toString()); return; }19        if (open < n) {20            sb.append('(');21            backtrack(n, open + 1, close, sb, res);22            sb.deleteCharAt(sb.length() - 1);23        }24        if (close < open) {25            sb.append(')');26            backtrack(n, open, close + 1, sb, res);27            sb.deleteCharAt(sb.length() - 1);28        }29    }30 31    public static void main(String[] args) {32        check(generateParenthesis(3).size() == 5, "case1");33        check(generateParenthesis(1).equals(Arrays.asList("()")), "case2");34        System.out.println("all tests passed");35    }36 37    static void check(boolean cond, String name) {38        if (!cond) throw new AssertionError("FAILED: " + name);39        System.out.println("  PASS " + name);40    }41}