自己解法

核心思想是已生成的括号字符串里，左括号数要大于等于右括号数，然后使用递归的思想，每一步可以走不同的左右括号的选择，直到最后生成合法的括号字符串为止。深度优先遍历的思想，自己写的时候因为没想好怎么做回溯，就直接用String保存了字符串，每次开辟新的空间，这种解法的空间复杂度较高。

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> resList = new ArrayList<>(16);

        generate(0, 0, n, "", resList);

        return resList;                                     

    }

    public void generate(int left, int right, int n, String res, List<String> resList) {

        if (left > n || right > n) {

            return;

        }

        if (left == n && right == n) {

            resList.add(res);

            return;

        }

        if (left >= right) {

            generate(left + 1, right, n, res + "(", resList);

            generate(left, right + 1, n, res + ")", resList);

        }

    }

}

官方解法

与自己解法思路类似，多了一遍回溯，用StringBuilder存放字符串结果，节省空间。

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> ans = new ArrayList();

        backtrack(ans, new StringBuilder(), 0, 0, n);

        return ans;

    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max){

        if (cur.length() == max * 2) {

            ans.add(cur.toString());

            return;

        }

        if (open < max) {

            cur.append('(');

            backtrack(ans, cur, open+1, close, max);

            cur.deleteCharAt(cur.length() - 1);

        }

        if (close < open) {

            cur.append(')');

            backtrack(ans, cur, open, close+1, max);

            cur.deleteCharAt(cur.length() - 1);

        }

    }

}