LeetCode-22-括号生成(Generate Parentheses)

22. 括号生成

难度中等1757收藏分享切换为英文接收动态反馈

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

22.Generate Parentheses

Medium

7676328Add to ListShare

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

方法一：暴力法

算法

为了生成所有序列，我们可以使用递归。长度为 n 的序列就是在长度为 n-1 的序列前加一个 '(' 或 ')'。

class Solution {
    // 不剪枝的做法
    public static List<String> generateParenthesis(int n) {
        char[] path = new char[n << 1];
        List<String> ans = new ArrayList<>();
        process2(path, 0, ans);
        return ans;
    }

    public static void process2(char[] path, int index, List<String> ans) {
        if (index == path.length) {
            if (isValid(path)) {
                ans.add(String.valueOf(path));
            }
        } else {
            path[index] = '(';
            process2(path, index + 1, ans);
            path[index] = ')';
            process2(path, index + 1, ans);
        }
    }

    public static boolean isValid(char[] path) {
        int count = 0;
        for (char cha : path) {
            if (cha == '(') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
}

image-20210430100622612

方法二：剪枝

数字 n 代表生成括号的对数，所以左左括号最多为n个，在做决策的时候，每当可以填入'('时候，int leftRest--

image-20210430101749468

image-20210430102006075

class Solution {
   public static List<String> generateParenthesis(int n) {
        char[] path = new char[n << 1];
        List<String> ans = new ArrayList<>();
        process(path, 0, 0, n, ans);
        return ans;
    }

    // 依次在path上填写决定
    // ( ( ) ) ( )....
    // 0 1 2 3 4 5
    // path[0...index-1]决定已经做完了
    // index位置上，( )
    //leftMinusRight  "(  -  )"的个数
    //leftRest  "(" 剩下可以决策的个数
    public static void process(char[] path, int index, int leftMinusRight, int leftRest, List<String> ans) {
        if (index == path.length) {
            ans.add(String.valueOf(path));
        } else {
            if (leftRest > 0) {
                path[index] = '(';//决策（ leftRest剩余的个数-1
                process(path, index + 1, leftMinusRight + 1, leftRest - 1, ans);
            }
            if (leftMinusRight > 0) {
                path[index] = ')';//决策） ）的个数+1 leftMinusRight-1
                process(path, index + 1, leftMinusRight - 1, leftRest, ans);
            }
        }
    }

}

image-20210430102306435