HHot 100C++ 图解

22. 括号生成

一句话套路open<n 才能加左,close<open 才能加右

题目描述

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

 

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

 

提示:

  • 1 <= n <= 8

思路

时间O(4^n / sqrt(n))

思路

任意前缀里「右括号数 <= 左括号数」才合法,所以只有两个约束:open < n 才能加 '(',close < open 才能加 ')'。走到长度 2n 收集。

这样生成出来的每个串都必然合法,无需事后校验 —— 好的状态定义让剪枝消失。

图解

( 0 ( 1 ( 2 ) 3 ) 4 ) 5 a a'
生成规则:能放左括号就放左;右括号只有当「已放右括号数 < 已放左括号数」时才放。最终长度 2n,且任意前缀 左≥右。

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/10_backtracking.cpp29 行
namespace lc0022 {
class Solution {
 public:
  vector<string> generateParenthesis(int n) {
    vector<string> ans;
    string path;
    dfs(n, 0, 0, path, ans);
    return ans;
  }

 private:
  static void dfs(int n, int open, int close, string& path, vector<string>& ans) {
    if ((int)path.size() == 2 * n) {
      ans.push_back(path);
      return;
    }
    if (open < n) {
      path.push_back('(');
      dfs(n, open + 1, close, path, ans);
      path.pop_back();
    }
    if (close < open) {  // 还没配对的左括号数 > 0 才能放右括号
      path.push_back(')');
      dfs(n, open, close + 1, path, ans);
      path.pop_back();
    }
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q22_generate_parentheses6 行
lc0022::Solution s;
CHECK_EQ(s.generateParenthesis(3),
         vector<string>{"((()))", "(()())", "(())()", "()(())", "()()()"});
CHECK_EQ(s.generateParenthesis(1), vector<string>{"()"});
CHECK_EQ(s.generateParenthesis(2).size(), (size_t)2);
CHECK_EQ(s.generateParenthesis(4).size(), (size_t)14);  // 卡特兰数

↑↓ 选择↵ 打开/ 随时唤起