回溯之Leetcode22 Generate Parentheses

本题大意就是求n个括号的全排列。这是题目链接：leetcode.22

方法就是一一枚举，用回溯来实现。有关回溯文章“回溯详解“讲的很详细，可以看看。

用left和right来表示左括号剩余的个数和右括号剩余的个数。

1. 如果left>right，说明括号不匹配，直接return。
2. 如果left==0&&right==0，说明找出一种排列。
3. 其余则分别添‘(’和‘)’递归。

class Solution {
public:vector<string> generateParenthesis(int n) {vector <string> ans;int left=n,right=n;string s="";dfs(left,right,s,ans);return ans;}void dfs(int l,int r,string s,vector <string> &v){if(l>r){return;}if(l==0&&r==0){v.push_back(s);return;}if(l>0){dfs(l-1,r,s+"(",v);}if(r>0){dfs(l,r-1,s+")",v);}}
};