括号生成

题目要求

设计一个函数，该函数接收一个整数 n 作为参数，这个整数代表括号对的数量。函数的目标是生成一个字符串列表，其中包含所有可能的、有效的括号组合。所谓“有效的括号组合”是指每一个组合中的括号都能正确闭合，没有任何多余或缺少的括号。

解题思路

生成有效括号组合的问题可以通过递归方法来解决。递归的基本思想是，我们在生成字符串的过程中，保持跟踪左括号和右括号的数量，并且确保在任何时刻插入括号的过程中，左括号的数量不小于右括号的数量（这样才能保证括号的有效性）。

以下是解题的步骤：

初始化：创建一个空列表来存储所有有效的括号组合。
递归函数设计：设计一个递归函数，该函数接收以下参数：
- 当前构造中的字符串 current
- 已使用的左括号数量 left
- 已使用的右括号数量 right
- 总的括号对数 n
递归终止条件：当 current 字符串的长度达到 2 * n 时，说明已经构造了一个有效的括号组合，将其添加到列表中。
递归过程：
- 如果 left 的数量小于 n，则可以添加一个左括号 '(' 并递归调用函数，因为添加左括号总是安全的。
- 如果 right 的数量小于 left，则可以添加一个右括号 ')' 并递归调用函数，因为只有当右括号的数量少于左括号的数量时，添加右括号才是有效的。
回溯：在每一步递归调用之后，需要回溯以撤销当前步骤的选择，继续尝试其他可能的路径。
返回结果：当递归完成后，返回存储所有有效括号组合的列表。

通过这种方式，我们可以确保生成的每个括号组合都是有效的，并且能够覆盖所有可能的组合。

Golang 版本

package main

import "fmt"

// generateParenthesis 生成所有有效的括号组合
func generateParenthesis(n int) []string {
    var result []string
    backtrack(&result, "", 0, 0, n)
    return result
}

// backtrack 是一个递归辅助函数，用于生成括号
func backtrack(result *[]string, current string, open, close, max int) {
    if len(current) == max*2 {
        *result = append(*result, current)
        return
    }

    if open < max {
        backtrack(result, current+"(", open+1, close, max)
    }
    if close < open {
        backtrack(result, current+")", open, close+1, max)
    }
}

func main() {
    n := 3
    combinations := generateParenthesis(n)
    for _, combination := range combinations {
        fmt.Println(combination)
    }
}

这段代码定义了一个 generateParenthesis 函数，它接收一个整数 n 并返回一个字符串切片，包含所有可能的有效括号组合。backtrack 函数是一个递归函数，用于构建括号组合。主函数 main 展示了如何调用 generateParenthesis 函数并打印结果。

C++版本

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        std::vector<std::string> result;
        generate(result, "", n, n);
        return result;
    }

private:
    void generate(std::vector<std::string> &result, std::string current, int open, int close) {
        if (open == 0 && close == 0) {
            result.push_back(current);
            return;
        }

        if (open > 0) {
            generate(result, current + "(", open - 1, close);
        }

        if (close > open) {
            generate(result, current + ")", open, close - 1);
        }
    }
};

int main() {
    Solution solution;
    int n = 3;
    std::vector<std::string> combinations = solution.generateParenthesis(n);
    for (const std::string &combination : combinations) {
        std::cout << combination << std::endl;
    }
    return 0;
}

这段 C++代码定义了一个 Solution 类，其中包含了 generateParenthesis 方法，用于生成所有有效的括号组合。generate 是一个私有辅助方法，用于递归生成括号组合。main 函数展示了如何创建 Solution 类的实例，调用 generateParenthesis 方法，并打印出所有的括号组合。

Python 版本

def generate_parenthesis(n):
    def backtrack(s='', left=0, right=0):
        if len(s) == 2 * n:
            result.append(s)
            return
        if left < n:
            backtrack(s + '(', left + 1, right)
        if right < left:
            backtrack(s + ')', left, right + 1)

    result = []
    backtrack()
    return result

# 示例
n = 3
print(generate_parenthesis(n))

这段 Python 代码定义了一个 generate_parenthesis 函数，它接收一个整数 n 并返回一个列表，包含所有可能的有效括号组合。内部定义了一个 backtrack 辅助函数，用于递归地构建括号组合。最后，代码中包含了一个示例调用和打印结果的过程。

Java 版本

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, String current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }

        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 3;
        List<String> combinations = solution.generateParenthesis(n);
        for (String combination : combinations) {
            System.out.println(combination);
        }
    }
}

这段 Java 代码定义了一个 Solution 类，其中包含了 generateParenthesis 方法，用于生成所有有效的括号组合。backtrack 是一个私有辅助方法，用于递归生成括号组合。main 方法展示了如何创建 Solution 类的实例，调用 generateParenthesis 方法，并打印出所有的括号组合。

Rust 版本

fn generate_parenthesis(n: i32) -> Vec<String> {
    fn backtrack(
        current: String,
        open: i32,
        close: i32,
        n: i32,
        result: &mut Vec<String>,
    ) {
        if current.len() as i32 == n * 2 {
            result.push(current);
            return;
        }
        if open < n {
            backtrack(current.clone() + "(", open + 1, close, n, result);
        }
        if close < open {
            backtrack(current.clone() + ")", open, close + 1, n, result);
        }
    }

    let mut result = Vec::new();
    backtrack(String::new(), 0, 0, n, &mut result);
    result
}

fn main() {
    let n = 3;
    let combinations = generate_parenthesis(n);
    for combination in combinations {
        println!("{}", combination);
    }
}

这段 Rust 代码定义了一个 generate_parenthesis 函数，它接收一个整数 n 并返回一个包含所有可能的有效括号组合的 Vec<String>。内部定义了一个 backtrack 辅助函数，用于递归地构建括号组合。main 函数展示了如何调用 generate_parenthesis 函数并打印出所有的括号组合。

总结

生成所有可能的有效括号组合的问题可以通过递归回溯算法来解决。无论是在 Golang、C++、Python 还是 Rust 中，核心算法的逻辑是相同的，主要步骤如下：

定义一个递归函数 backtrack，它接受当前构建的字符串 current，已放置的左括号数量 open，已放置的右括号数量 close，以及括号对的总数 n。
递归的终止条件是 current 字符串的长度等于 n * 2，这时将 current 添加到结果集中。
在每一步递归中，可以选择添加一个左括号或一个右括号，但需要满足以下条件：
- 左括号的数量不能超过 n。
- 右括号的数量不能超过左括号的数量，以确保括号的有效性。
如果左括号的数量小于 n，则添加一个左括号，并递归调用 backtrack。
如果右括号的数量小于左括号的数量，则添加一个右括号，并递归调用 backtrack。
通过递归回溯，可以探索所有可能的括号组合，并最终生成一个包含所有有效组合的列表。

在实现上，每种语言都有其特定的语法和数据结构，但整体算法框架保持一致。例如，在 Rust 中使用 String 和 Vec<String>，在 Python 中使用字符串和列表，而在 C++ 和 Java 中则使用 std::string 和 std::vector<std::string> 或 String 和 List<String>。主函数通常用于演示如何调用生成括号组合的函数，并打印结果。

hot-100