括号

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
通过次数12,382提交次数15,243

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bracket-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯

1. 如果左括号的数量小于n，可以继续添加左括号
2. 如果右括号的数量小于左括号，可以继续添加右括号

class Solution {
    public List<String> generateParenthesis(int n) {
        if (n == 0) return new ArrayList<>();
        Set<String> set = new HashSet<>();

        backtrack(n * 2, new StringBuilder(), set, 0, 0);

        return new ArrayList<>(set);
    }

    public void backtrack(int n, StringBuilder bd, Set<String> set, int leftNum, int rightNum) {
        if (bd.length() == n) {
            String thesis = bd.toString();
            if (isValid(thesis)) set.add(thesis);
            return;
        }
        if (leftNum < n / 2) {
            bd.append("(");
            backtrack(n, bd, set, leftNum + 1, rightNum);
            bd.deleteCharAt(bd.length() - 1);
        }
        if (rightNum < leftNum) {
            bd.append(")");
            backtrack(n, bd, set, leftNum, rightNum + 1);
            bd.deleteCharAt(bd.length() - 1);
        }
    }
    public boolean isValid(String thesis) {
        int count = 0;
        for (int i = 0; i < thesis.length(); i++) {
            if (thesis.charAt(i) == '(') count++;
            else count--;
            if (count < 0) return false;
        }
        return count == 0;
    }
}

赏

谢谢你请我吃糖果

微信