原题链接🔗：括号生成
难度：中等⭐️⭐️
题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
1 <= n <= 8
递归
递归是一种在计算机科学中常用的编程技术，它允许函数调用自身。递归函数通常用于解决可以被分解为相似子问题的问题。递归的关键点在于找到问题的基本情况（base
case）和递归步骤（recursive case）。
递归的基本概念
- 基本情况（Base Case）：递归函数必须有一个或多个停止条件，这些条件不需要进一步递归调用。当达到这些条件时，函数将返回一个值。
- 递归步骤（Recursive Case）：在递归步骤中，函数会调用自身，并且每次调用都会使问题更接近基本情况。
递归的步骤
- 定义问题：首先定义需要解决的问题。
- 确定基本情况：找出问题的基本情况，即不需要进一步递归调用的情况。
- 递归调用：在函数中调用自身，每次调用都使问题更接近基本情况。
- 组合结果：将递归调用的结果组合起来，形成最终的解决方案。
递归的应用
- 图形和树的遍历（如深度优先搜索）
- 排序算法（如快速排序和归并排序）
- 动态规划问题
- 字符串处理（如字符串匹配和编辑距离）
递归的注意事项
- 避免无限递归：确保递归调用能够达到基本情况，避免无限递归。
- 优化递归：递归可能会导致大量的重复计算，可以通过记忆化递归来优化性能。
- 栈溢出：递归深度过大可能会导致栈溢出，因此需要考虑递归的深度。
示例：计算阶乘 下面是一个使用递归计算阶乘的示例代码：
#include <iostream>
>
> int factorial(int n) {
> if (n == 0) { // 基本情况
> return 1;
> } else { // 递归步骤
> return n * factorial(n - 1);
> } }
>
> int main() {
> int n;
> std::cout << "Enter a number: ";
> std::cin >> n;
> std::cout << "Factorial of " << n << " is " << factorial(n) << std::endl;
> return 0; }
在这个示例中：
factorial函数是一个递归函数，它计算一个数的阶乘。- 当
n等于 0 时，函数返回 1（基本情况）。- 否则，函数返回
n * factorial(n - 1)（递归步骤）。递归是一种强大的工具，但也需要谨慎使用，以避免潜在的问题。
回溯算法
回溯算法是一种通过试错来解决问题的算法，它尝试分步地去解决一个问题。在分步解决问题的过程中，如果某一步不符合要求，就会回退到上一步（回溯），然后选择另外一种方式继续尝试。回溯算法通常用于解决组合问题、排列问题、生成问题等。
- 回溯算法的基本思想
- 选择：从问题的候选解中选择一个解，通常是一个部分解。
- 扩展：将选择的解扩展为更接近最终解的形式。
- 剪枝：在扩展过程中，如果发现当前的解不可能产生最终解，就停止继续扩展，回退到上一步。
- 回溯：当扩展到某一步发现当前路径不能得到解时，就回退到上一步，重新选择其他候选解继续尝试。
- 回溯算法的步骤
- 定义问题：明确需要解决的问题，并确定问题的候选解。
- 确定候选解：列出所有可能的候选解。
- 递归函数：设计一个递归函数，用于尝试不同的候选解。
- 剪枝：在递归过程中，根据问题的特点，剪去那些不可能产生解的候选解。
- 回溯：当发现当前路径不能得到解时，回退到上一步，重新选择候选解。
- 回溯算法的应用
- 八皇后问题
- 素数生成
- 括号生成
- 数独问题
- 图的着色问题
题解
- 解题思路：
LeetCode 上的“括号生成”问题是一个经典的递归问题，主要考察的是回溯算法。这个问题要求你生成所有可能的括号组合，确保每个括号都有一个匹配的配对。
- 理解问题：首先需要理解什么是有效的括号组合。有效的括号组合意味着每个左括号 ‘(’ 都有一个对应的右括号 ‘)’，并且右括号不能在左括号之前。
- 递归方法：使用递归方法生成括号。递归的基本思路是：
- 从左到右逐个添加括号。
- 在每一步，可以选择添加左括号 ‘(’ 或者右括号 ‘)’。
- 确保在添加右括号 ‘)’ 之前，左括号 ‘(’ 的数量不少于右括号的数量。
- 回溯：每次递归时，尝试添加一个括号，然后回溯到上一步，尝试添加另一种括号。这样能够生成所有可能的组合。
- 终止条件：当生成的括号数量达到 2n 时，返回当前生成的字符串，因为 n 个左括号和 n 个右括号已经完全匹配。
- c++ demo:
#include <iostream>
#include <vector>
#include <string>
class Solution {
public:
std::vector<std::string> generateParenthesis(int n) {
std::vector<std::string> result;
backtrack(result, "", 0, 0, n);
return result;
}
private:
void backtrack(std::vector<std::string>& result, std::string current, int open, int close, int max) {
if (current.length() == 2 * max) {
result.push_back(current);
return;
}
if (open < max) {
backtrack(result, current + '(', open + 1, close, max);
}
if (close < open) {
backtrack(result, current + ')', open, close + 1, max);
}
}
};
int main() {
Solution solution;
int n;
std::cout << "Enter the number of pairs of parentheses: ";
std::cin >> n;
std::vector<std::string> parentheses = solution.generateParenthesis(n);
std::cout << "Total combinations: " << parentheses.size() << std::endl;
for (const std::string& s : parentheses) {
std::cout << s << std::endl;
}
return 0;
}
- 输出结果：
Enter the number of pairs of parentheses: 4
Total combinations: 14
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
- 代码仓库地址：generateParenthesis
