Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
实现思路:
首先如果采用回溯算法去做题目一般都可以折射成N叉树的一个模型,然后采用回溯算法的代码模板来去做。
本题的规律是:
1.左括号'('的个数始终是大于等于右括号的')',所以当遍历到右括号多的时候就可以进行剪枝操作了,所以只有左括号还能输出的个数严格小于右括号的时候 才能进行输出右括号。
2.当左右括号还能输出的个数都为0的时候则为一组结果
AC代码:
class Solution {
vector<string> ans;
void dfs(string str,int left,int right) {
if(left==0&&right==0) {
ans.push_back(str);
return;
}
if(left>right) return;//剪枝
if(left>0)
dfs(str+'(',left-1,right);
if(left<right)//左括号还能输出的个数严格小于右括号的个数
dfs(str+')',left,right-1);
}
public:
vector<string> generateParenthesis(int n) {
dfs("",n,n);
return ans;
}
};