代码1

backtrack
Runtime: 1 ms, faster than 84.99% of Java online submissions for Generate Parentheses.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList();
        backtrack(list, "", 0, 0, n);
        return list;
    } 
    public void backtrack(List<String> list, String s, int open, int close, int n) {
        if (s.length() == n * 2) {
            list.add(s);
            return;
        }
        if (open < n) {
            backtrack(list, s + "(", open + 1, close, n);
        }
        if (close < open) {
            backtrack(list, s + ")", open, close + 1, n);
        }
    }
}

代码1

dp
Runtime: 12 ms, faster than 5.40% of Java online submissions for Generate Parentheses.

class Solution {
    public List generateParenthesis(int max) {
        List<List<String>> list = new LinkedList();
        list.add(Arrays.asList(""));
        for (int i = 1; i <= max; i++) {
            List<String> nlist = new LinkedList();
            for (int j = 0; j < i; j++) {
                List<String> inside = list.get(j);
                List<String> tail = list.get(i - j - 1);
                for (int n = 0; n < inside.size(); n++) {
                    for (int m = 0; m < tail.size(); m++) {
                        nlist.add("(" + inside.get(n) + ")" + tail.get(m));
                    }
                }
            }
            list.add(nlist);
        }
        return list.get(max);
    }
}