原文链接: https://leetcode-cn.com/problems/IDBivT

中文题目

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= n <= 8

 

注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

通过代码

高赞题解

在学习回溯算法之前，你最好对树的 DFS 熟悉，因为回溯的问题基本都可以抽象成树形结构问题。

你之所以觉得回溯难，是因为你的树形结构及其算法不熟悉。

如果树的 DFS 不熟悉的话，或者想全面系统的学习回溯、贪心和动态规划的话，请看这里：构建数据结构与算法的知识体系。

1. 将问题抽象成树形结构遍历问题

代码如下：

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    if (n <= 0) return res;
    dfs(n, "", res);
    return res;
}

private void dfs(int n, String path, List<String> res) {
    if (path.length() == 2 * n) {
        res.add(path);
        return;
    }

    dfs(n, path + "(", res);
    dfs(n, path + ")", res);
}

2. 剪枝策略

代码如下：

[]
public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    if (n <= 0) return res;
    dfs(n, "", res, 0, 0);
    return res;
}

private void dfs(int n, String path, List<String> res, int open, int close) {
    if (open > n || close > open) return;

    if (path.length() == 2 * n) {
        res.add(path);
        return;
    }

    dfs(n, path + "(", res, open + 1, close);
    dfs(n, path + ")", res, open, close + 1);
}

[]
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n <= 0) return res;
        dfs(n, "", res, 0, 0);
        return res;
    }

    void dfs(int n, string path, vector<string>& res, int open, int close) {
        if (open > n || close > open) return;

        if (path.length() == 2 * n) {
            res.push_back(path);
            return;
        }

        dfs(n, path + "(", res, open + 1, close);
        dfs(n, path + ")", res, open, close + 1);
    }

[]
def generateParenthesis(self, n: int) -> List[str]:
    res = []
    if n <= 0: return res

    def dfs(path, open, close) -> None:
        if open > n or close > open:
            return
        if len(path) == 2 * n:
            res.append(path)
            return

        dfs(path + "(", open + 1, close)
        dfs(path + ")", open, close + 1)

    dfs("", 0, 0)
    return res

[]
var generateParenthesis = function(n) {
    const res = []
    if (n <= 0) return res

    const dfs = (path, open, close) => {
        if (open > n || close > open) return
        if (path.length == 2 * n) {
            res.push(path)
            return
        }
        dfs(path + "(", open + 1, close)
        dfs(path + ")", open, close + 1)
    }

    dfs("", 0, 0)
    return res
};

3. 另一种代码实现

代码如下：

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    if (n <= 0) return res;
    dfs(n, "", res, 0, 0);
    return res;
}

private void dfs(int n, String path, List<String> res, int open, int close) {
    if (path.length() == 2 * n) {
        res.add(path);
        return;
    }
    if (open < n) {
        dfs(n, path + "(", res, open + 1, close);
    }
    if (close < open) {
        dfs(n, path + ")", res, open, close + 1);
    }
}

在刷题的时候：

1. 如果你觉得自己数据结构与算法基础不够扎实，那么请点这里，这里包含了一个程序员 5 年内需要的所有算法知识。

2. 如果你感觉刷题太慢，或者感觉很困难，或者赶时间，那么请点这里。这里用 365 道高频算法题，带你融会贯通算法知识，做到以不变应万变。

3. 回溯、贪心和动态规划，是算法面试中的三大难点内容，如果你只是想搞懂这三大难点内容 请点这里。

以上三个链接中的内容，都支持 Java/C++/Python/js 四种语言

统计信息

通过次数	提交次数	AC比率
4798	5637	85.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言