【leetcode-22】括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

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

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

回溯法

回溯算法基本思想：能进则进，进不了则换，换不了则退

括号生成算法类似于二叉树先序遍历
可用递归生成问题解空间树
再用剪枝函数来对解空间树进行剪枝
括号生成:

进入左子树条件： ( 括号小于 n
进入右子树条件：）括号小于（括号

核心思路：如果括号有效，任意位置的左括号是要大于等于右括号的，即如果左括号等于右括号数量，那么接下来的操作一定是加入左括号；如果左括号大于右括号，有两种选择，出左括号或右括号。如果做括号数量已经为最大值，只需要将剩下的右括号补齐即可。

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> ans = new ArrayList();

        backtrack(ans, "", 0, 0, n);

        return ans;

    }

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

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

            ans.add(cur);

            return;

        }

        if (open < max)

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

        if (close < open)

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

    }

}

上面的解法写详细些如下，一样的思路：

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> result = new ArrayList<>();

        generate(0, 0, new StringBuilder(), n, result);

        return result;

    }

    public static void generate(int left, int right, StringBuilder sb, int n, List<String> result) {

        //若该位置可以填左括号，则尝试选填左括号

        if (left < n) {

            sb.append("(");

            left++;

            //填完左括号，往下继续调用填下一个位置，此时left即已完成部分左括号填写数加1

            generate(left, right, sb, n, result);

            //删除填左括号的操作，即还原数据，尝试执行下个if填右括号

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

            left--;

        }

        // 若已经填的位置中，左括号大于右括号数，则该位置可以填右括号

        if (right < left) {

            sb.append(")");

            right++;

            generate(left, right, sb, n, result);

            //还原字符串

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

            right--;

        }

        //如果所有的位置都已经填好，则符合要求的结果

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

            result.add(sb.toString());

        }

    }

}

巴特西

【leetcode-22】括号生成

回溯法

最新文章

热门文章