22. 括号生成【 力扣(LeetCode) 】

零、原题链接

22. 括号生成

一、题目描述

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

二、测试用例

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

三、解题思路

1. 基本思路：
     回溯 + 剪枝
2. 具体思路：
   • 编写回溯函数 dfs：
     • 如果括号都放完了，则记录到答案中；
     • 如果剩余左括号数多余又括号，说明括号序列不合法，则回溯；【剪枝】
     • 如果左括号还有剩，则该位置放置左括号，递归调用 dfs 函数，确定下一个位置；
     • 如果右括号还有剩，则该位置放置右括号，递归调用 dfs 函数，确定下一个位置；
   • 调用 dfs 函数
   • 返回结果。

四、参考代码

时间复杂度：$\mathrm{O}(2^n)$
空间复杂度：$\mathrm{O}(n)$

class Solution {
public:vector<string> ans;string str;void dfs(const int& left, const int& right) {if (left == 0 && right == 0) {ans.emplace_back(str);return;}if (left > right)return;if (left > 0) {str.push_back('(');dfs(left - 1, right);str.pop_back();}if (right > 0) {str.push_back(')');dfs(left, right - 1);str.pop_back();}}vector<string> generateParenthesis(int n) {dfs(n, n);return ans;}
};