LeetCode 算法：括号生成 c++

原题链接🔗：括号生成
难度：中等⭐️⭐️

题目

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

示例 1：

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

示例 2：

输入：n = 1
输出：[“()”]

提示：

1 <= n <= 8

递归

递归是一种在计算机科学中常用的编程技术，它允许函数调用自身。递归函数通常用于解决可以被分解为相似子问题的问题。递归的关键点在于找到问题的基本情况（base
case）和递归步骤（recursive case）。

• 递归的基本概念

  1. 基本情况（Base Case）：递归函数必须有一个或多个停止条件，这些条件不需要进一步递归调用。当达到这些条件时，函数将返回一个值。
  2. 递归步骤（Recursive Case）：在递归步骤中，函数会调用自身，并且每次调用都会使问题更接近基本情况。

• 递归的步骤

  1. 定义问题：首先定义需要解决的问题。
  2. 确定基本情况：找出问题的基本情况，即不需要进一步递归调用的情况。
  3. 递归调用：在函数中调用自身，每次调用都使问题更接近基本情况。
  4. 组合结果：将递归调用的结果组合起来，形成最终的解决方案。

• 递归的应用

  • 图形和树的遍历（如深度优先搜索）
  • 排序算法（如快速排序和归并排序）
  • 动态规划问题
  • 字符串处理（如字符串匹配和编辑距离）

• 递归的注意事项

  • 避免无限递归：确保递归调用能够达到基本情况，避免无限递归。
  • 优化递归：递归可能会导致大量的重复计算，可以通过记忆化递归来优化性能。
  • 栈溢出：递归深度过大可能会导致栈溢出，因此需要考虑递归的深度。

• 示例：计算阶乘 下面是一个使用递归计算阶乘的示例代码：

 #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)（递归步骤）。

递归是一种强大的工具，但也需要谨慎使用，以避免潜在的问题。

回溯算法

回溯算法是一种通过试错来解决问题的算法，它尝试分步地去解决一个问题。在分步解决问题的过程中，如果某一步不符合要求，就会回退到上一步（回溯），然后选择另外一种方式继续尝试。回溯算法通常用于解决组合问题、排列问题、生成问题等。

• 回溯算法的基本思想
  • 选择：从问题的候选解中选择一个解，通常是一个部分解。
  • 扩展：将选择的解扩展为更接近最终解的形式。
  • 剪枝：在扩展过程中，如果发现当前的解不可能产生最终解，就停止继续扩展，回退到上一步。
  • 回溯：当扩展到某一步发现当前路径不能得到解时，就回退到上一步，重新选择其他候选解继续尝试。
• 回溯算法的步骤
  • 定义问题：明确需要解决的问题，并确定问题的候选解。
  • 确定候选解：列出所有可能的候选解。
  • 递归函数：设计一个递归函数，用于尝试不同的候选解。
  • 剪枝：在递归过程中，根据问题的特点，剪去那些不可能产生解的候选解。
  • 回溯：当发现当前路径不能得到解时，回退到上一步，重新选择候选解。
• 回溯算法的应用
  • 八皇后问题
  • 素数生成
  • 括号生成
  • 数独问题
  • 图的着色问题

题解

1. 解题思路：

LeetCode 上的“括号生成”问题是一个经典的递归问题，主要考察的是回溯算法。这个问题要求你生成所有可能的括号组合，确保每个括号都有一个匹配的配对。

• 理解问题：首先需要理解什么是有效的括号组合。有效的括号组合意味着每个左括号 ‘(’ 都有一个对应的右括号 ‘)’，并且右括号不能在左括号之前。
• 递归方法：使用递归方法生成括号。递归的基本思路是：
  • 从左到右逐个添加括号。
  • 在每一步，可以选择添加左括号 ‘(’ 或者右括号 ‘)’。
  • 确保在添加右括号 ‘)’ 之前，左括号 ‘(’ 的数量不少于右括号的数量。
• 回溯：每次递归时，尝试添加一个括号，然后回溯到上一步，尝试添加另一种括号。这样能够生成所有可能的组合。
• 终止条件：当生成的括号数量达到 2n 时，返回当前生成的字符串，因为 n 个左括号和 n 个右括号已经完全匹配。

2. 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
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

3. 代码仓库地址：generateParenthesis