面试题 08.09. 括号

题目：

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

题解：

采用回溯的思想，边界条件是字符串temp的长度是n*2的时候终止，并返回。

把字符串temp追加到不定长数组vec后面

如果左括号少于n，则添加左括号

如果右括号少于左括号，则添加右括号

代码：

 1 class Solution {
 2     vector<string> vec;
 3 public:
 4     //采用回溯的思想，边界条件是字符串temp的长度是n*2的时候终止，并返回。
 5     void dfs(int l,int r,string temp,int n)
 6     {
 7         if(temp.length()==n*2)
 8         {
 9             vec.push_back(temp);//把字符串temp追加到不定长数组vec后面
10         }
11         if(l<n)//如果左括号少于n，则添加左括号
12         dfs(l+1,r,temp+'(',n);
13         if(r<l)//如果右括号少于左括号，则添加右括号
14         {
15             dfs(l,r+1,temp+')',n);
16         }
17     }
18     vector<string> generateParenthesis(int n) {
19         dfs(0,0,"",n);//dfs的初始条件
20         return vec;//返回字符串不定长数组vec
21     }
22 };

 

 

 

 

 

 

参考链接：https://leetcode-cn.com/problems/bracket-lcci

https://leetcode-cn.com/problems/bracket-lcci/solution/c-by-fanko/