LeetCode22.括号生成
LeetCode22.括号生成

LeetCode22.括号生成

以前写过的回溯算法基本都是只需要一次回溯操作的,这道题思路不太一样,需要把左括号和右括号都分别回溯一次,剪枝条件是判断左括号数量大于n或右括号数量大于n或右括号数量大于左括号数量

代码如下:

class Solution {

    private List<String> list = new ArrayList<>();
    private StringBuilder path = new StringBuilder();

    private void backtracking(int leftCount, int rightCount, int n) {
        if (leftCount > n || rightCount > n ||rightCount > leftCount) return;
        if (path.length() == 2 * n) {
            list.add(new String(path));
            return;
        }

        path.append("(");
        backtracking(leftCount + 1, rightCount, n);
        path.deleteCharAt(path.length() - 1);

        path.append(")");
        backtracking(leftCount, rightCount + 1, n);
        path.deleteCharAt(path.length() - 1);
    }

    public List<String> generateParenthesis(int n) {
        backtracking(0, 0, n);
        return list;
    }
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注