22. 括号生成

题目描述

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

解题思路

本题是回朔法的模板题，利用此题可以归纳出简单的回朔法模板。

回朔法和深度优先遍历相似，经典的回朔法应用包括八皇后问题、排列组合问题等。

从抽象的层面看，这些问题都有共同的特点：

  • 当我们已经得到某个可行解的一部分时，下一步往往有好几种选择，每种选择都代表一条新的分支
  • 当我们顺着某条分支走到头后，就得到了一个完整的可行解
  • 问题一般都要求输出所有可行解

从实现的层面看，如果用递归的方法来实现回朔法，也有编码上的共同特点：

  • 递归函数的参数列表中，有一个引用传递的参数用来维护所有可行解的集合

    • 当算法找到可行解后，将可行解加入该集合中

  • 递归函数的参数列表中，需要有值传递的一系列参数用来维护当前的状态

    • 这个状态既能告诉我们已经获得的部分解
    • 又能告诉我们离完整的解还有多远

  • 递归函数体内，需要选择下一步如何扩展当前解

    • 一般有好几种选择分支，每种if分支内部都需要递归调用本函数
    • 递归调用时，参数列表中，要更新值传递的状态参数

  • 递归函数的返回类型一般为空

    • 如果找到完整的可行解，将可行解加入集合后，直接返回
    • 所有的递归调用结束后，函数返回

复杂度分析

时间复杂度：22. 括号生成 - 图1
空间复杂度：O(N)

知识点

回朔法，括号匹配，字符串

代码

  1. class Solution {
  2. public:
  3.     vector<string> generateParenthesis(int n) {
  4.         vector<string> res;
  5.         appendParenthesis(n, n, "", res);
  6.         return res;
  7.     }
  9.     void appendParenthesis(int leftCnt, int rightCnt, string s, vector<string>& res) {
  10.         if (leftCnt == 0 && rightCnt == 0) {
  11.             res.push_back(s);
  12.             return;
  13.         }
  14.         if (leftCnt) {
  15.             appendParenthesis(leftCnt - 1, rightCnt, s + "(", res);
  16.         }
  17.         if (rightCnt > leftCnt) {
  18.             appendParenthesis(leftCnt, rightCnt - 1, s + ")", res);
  19.         }
  20.         return;
  21.     }
  22. };

参考资料

  1. Leetcode官方题解