leetcode：22. 括号生成

题目

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

示例：

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

解答 & 代码

递归回溯

合法括号串 s 的性质：

  • 左括号的数量一定等于右括号的数量

  • 对于字符串的任意位置 i，s[0,...,i] 包含的左括号数量 >= 右括号数量

    1. class Solution {
    2. private:
    3.   vector<string> resultList;    // 存储所有可能的结果
    4.   string curResult;            // 存储当前生成的括号字符串
    6.   // 递归回溯，
    7.   // 定义：传入未使用的左括号数量 leftCnt 和未使用的右括号数量 rightCnt，生成合法的括号字符串
    8.   void dfs(int leftCnt, int rightCnt)
    9.   {
    10.       // 递归结束条件 1: 若剩余未使用左括号数量大于剩余未使用的右括号数量
    11.       // 说明当前生成的 curResult 中左括号数量大于右括号数量，肯定不合法，直接返回
    12.       if(leftCnt > rightCnt)
    13.           return;
    14.       // 递归结束条件 2: 如果左、右括号都已用完，则直接将当前结果存入结果数组，并返回
    15.       if(leftCnt == 0 && rightCnt == 0)
    16.       {
    17.           resultList.push_back(curResult);
    18.           return;
    19.       }
    21.       // 如果当前还有未使用的左括号，则在 curResult 尾部加上左括号
    22.       if(leftCnt > 0)
    23.       {
    24.           curResult += '(';                // 选择
    25.           dfs(leftCnt - 1, rightCnt);        // 递归
    26.           curResult.pop_back();            // 撤销选择
    27.       }
    28.       // 如果当前未使用的右括号数量大于未使用的左括号数量，则在 curResult 尾部加上右括号
    29.       if(rightCnt > leftCnt)
    30.       {
    31.           curResult += ')';                // 选择
    32.           dfs(leftCnt, rightCnt - 1);        // 递归
    33.           curResult.pop_back();            // 撤销选择
    34.       }
    36.   }
    37. public:
    38.   vector<string> generateParenthesis(int n) {
    39.       dfs(n, n);
    40.       return resultList;
    41.   }
    42. };

    复杂度分析：设括号对数为 N

  • 时间复杂度 O(？)：如果不剪枝，最终生成的字符串长为 2N，每个位置都有两种选择（'(' or')'），因此时间复杂度 [中等] 22. 括号生成 - 图1。但本题做了剪枝

  • 空间复杂度 O(N)：递归深度 2N

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：11.4 MB, 在所有 C++ 提交中击败了 56.35% 的用户