LeetCode热题100 括号生成

题目描述

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

示例 1：

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

示例 2：

输入：n = 1
输出：[“()”]

提示：

1 <= n <= 8

思路

1 当左边的数量>右边的数量，继续放右边一定是合法的。
2 直接进行递归，每次可以选择左边或者右边。
3 可以进行剪枝，当左边用完了就不能选择左边，当右边的数量等于左边的时候也不能选择右边。

代码

classSolution{public:vector<string>generateParenthesis(intn){vector<string>ans;string s;// n个左边和n个右边dfs(n,n,s,ans);returnans;}voiddfs(intleft_num,intright_num,string&s,vector<string>&ans){if(left_num==0&&right_num==0){ans.push_back(s);return;}// 1 选择左边if(left_num>0){s.push_back('(');dfs(left_num-1,right_num,s,ans);s.pop_back();}// 2 选择右边if(right_num>left_num){s.push_back(')');dfs(left_num,right_num-1,s,ans);s.pop_back();}}};