题目：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
思路：
在括号没有完全匹配之前，右括号的使用数量应当小于左括号的使用数量。
使用递归完成括号生成任务。
Python解法：
1 class Solution: 2 def generateParenthesis(self, n: int) -> List[str]: 3 res = [] 4 cur_str = '' 5 6 def dfs(cur_str, left, right): # left: 左括号还可以使用的个数； right: 右括号还可以使用的个数 7 if left == 0 and right == 0: 8 res.append(cur_str) 9 return 10 if right < left: # 生成括号的过程中，右括号使用的个数是不能多于左括号使用的个数的 11 return 12 if left > 0: 13 dfs(cur_str + '(', left - 1, right) 14 if right > 0: 15 dfs(cur_str + ')', left, right - 1) 16 17 dfs(cur_str, n, n) 18 return res
C++解法：
1 #include "pch.h" 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 using namespace std; 6 7 class Solution { 8 public: 9 vector<string> list; 10 vector<string> generateParenthesis(int n) { 11 _gen(n, n, ""); 12 return list; 13 } 14 15 void _gen(int leftRemain, int rightRemain, string tempResult) { 16 if(leftRemain == 0 && rightRemain == 0) { 17 list.push_back(tempResult); 18 return; 19 } 20 if(rightRemain < leftRemain) 21 return; 22 if (leftRemain > 0) 23 _gen(leftRemain - 1, rightRemain, tempResult + "("); 24 if (rightRemain > 0) 25 _gen(leftRemain, rightRemain - 1, tempResult + ")"); 26 } 27 }; 28 29 int main() { 30 Solution s; 31 for (auto c : s.generateParenthesis(3)) 32 cout << c << " "; // ((())) (()()) (())() ()(()) ()()() 33 }