括号生成（Python and C++解法）

题目：

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

思路：

　　在括号没有完全匹配之前，左括号的数量应当小于右括号的数量。使用递归完成括号生成任务。

Python解法：

 1 class Solution(object):
 2     def generate_parenthesis(self, n):
 3         self.list = []  # 存储最终结果
 4         self._gen(0, 0, n, "")  # 初始化，""之间不能有空格
 5         return self.list
 6 
 7     def _gen(self, left_used, right_used, n, result):  # left_used:左括号使用的个数；right_used：右括号使用的个数
 8         if left_used == n and right_used == n:  # 递归终止条件
 9             self.list.append(result)  # 往最终结果中加入当前结果
10             return
11         if left_used < n:  # 最后一个括号不能是左括号，所以不能取等于号
12             self._gen(left_used+1, right_used, n, result+"(")
13         if right_used <= n and right_used < left_used:  # 当right_used<n时，还必须满足right_used < left_used
14             self._gen(left_used, right_used+1, n, result+")")
15 
16 
17 if __name__ == '__main__':
18     s = Solution()
19     print(s.generate_parenthesis(3))  # ['((()))', '(()())', '(())()', '()(())', '()()()']

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(0, 0, n, "");
12         return list;
13     }
14 
15     void _gen(int leftUsed, int rightUsed, int n, string result) {
16         if (leftUsed == n && rightUsed == n) {
17             list.push_back(result);
18             return;
19         }
20         if (leftUsed < n)  // 最后一个括号不能是左括号，所以不能取等于号
21             _gen(leftUsed + 1, rightUsed, n, result + "(");
22         if (rightUsed <= n && rightUsed < leftUsed)  // 当right_used<=n时，还必须满足right_used < left_used
23             _gen(leftUsed, rightUsed + 1, n, result + ")");
24     }
25 };
26 
27 int main() {
28     Solution s;
29     for (auto c : s.generateParenthesis(3))
30         cout << c << " ";  // ((())) (()()) (())() ()(()) ()()()
31 }