题目

image.png

思路

老熟人了，依然是回溯+剪枝。具体是：递归，对于每一层，如果i等于0则添加左括号，否则添加右括号，并通过两个参数left和right记录当前所剩左括号和右括号的个数以达到剪枝的目的,并且当前所剩右括号数必须大于等于左括号数否则必是不符合要求的组合。

code

class Solution {
    private void traceBack(int n, int cur, int left, int right, StringBuilder sb, List<String> lists) {

        if (cur == 2 * n) {
            lists.add(sb.toString());
        } else {
            for (int i = 0; i < 2; i++) {
                if (i == 0 && left > 0) {
                    left--;
                    sb.append("(");
                    traceBack(n, cur + 1, left, right, sb, lists);
                    left++;
                    sb.deleteCharAt(sb.length() - 1);
                } else if (i == 1 && right > 0 && right > left) {
                    right--;
                    sb.append(")");
                    traceBack(n, cur + 1, left, right, sb, lists);
                    right++;
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }

    }

    public List<String> generateParenthesis(int n) {
        List<String> lists = new ArrayList<>();
        traceBack(n, 0, n, n, new StringBuilder(), lists);
        return lists;
    }
}