22. 括号生成

题目描述

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

解答

class Solution {
public:vector<string> res;// left:剩余可用左括号数// right:剩余可用右括号数void dfs(string str, int left, int right){if(left == 0 && right == 0){res.push_back(str);return ;}if(left == right) // 确保左括号 大于等于 右括号{dfs(str + '(', left - 1, right);}else if(left < right){if(left > 0){dfs(str + '(', left - 1, right);}dfs(str + ')', left, right - 1);}}vector<string> generateParenthesis(int n) {// 核心思路：生成左右括号时，要满足：左括号数 >= 右括号数// 推出：剩余左括号数 <= 右括号数dfs("", n, n);return res;}
};