目录
题目链接
注意点
解法
小结
题目链接
注意点
解法
解法一: 递归. 当 left>right 的时候返回(为了防止出现 )( )
- class Solution {
- public:
- void recursion(int left,int right,string str,vector<string> &ret)
- {
- if(left> right) return;
- else if(left== 0&& right == 0) ret.push_back(str);
- if(left> 0) recursion(left-1,right,str+"(",ret);
- if(right> 0)recursion(left,right-1,str+")",ret);
- }
- vector<string> generateParenthesis(int n) {
- vector<string> ret;
- recursion(n,n,"",ret);
- return ret;
- }
- };
解法二: 网上看来的方法. 也需要递归, 把 n-1 中生成的字符串中的每一个 ( 后面加上一个() 然后把和这个(配对的) 一起去掉. 最后加上一个 () 就形成了所有完整的情况. 因为过程中会出现重复的情况, 所以用 set 来保存过程形成的串.
- class Solution {
- public:
- vector<string> generateParenthesis(int n) {
- set<string> s;
- if(n == 0) s.insert("");
- else
- {
- vector<string> pre = generateParenthesis(n-1);
- for(auto p:pre)
- {
- for(auto i = 0;i <p.size();i++)
- {
- if(p[i] == '(')
- {
- p.insert(p.begin()+i+1,'(');
- p.insert(p.begin()+i+2,')');
- s.insert(p);
- p.erase(p.begin() + i + 1, p.begin() + i + 3);
- }
- }
- s.insert("()"+p);
- }
- }
- return vector<string>(s.begin(),s.end());
- }
- };
解法三: dfs.
- class Solution {
- public:
- void dfs(int n, int left, int right, string str, vector<string> &ret)
- {
- if(left <n)
- {
- dfs(n,left+1,right,str+"(",ret);
- }
- if(right < left)
- {
- dfs(n,left,right+1,str+")",ret);
- }
- if(str.size() == n*2)
- {
- ret.push_back(str);
- }
- }
- vector<string> generateParenthesis(int n) {
- vector<string> ret;
- dfs(n, 0, 0, "", ret);
- return ret;
- }
- };
小结
一般 DFS:
- void dfs()
- {
- if(符合边界条件)
- {
- ///////
- return;
- }
- dfs();// 某种形式的调用
- }
带回溯的 DFS:
- void dfs(int 当前状态)
- {
- if(当前状态为边界状态)
- {
- // 记录或输出
- return;
- }
- for(i=0;i<n;i++) // 横向遍历解答树所有子节点
- {
- // 扩展出一个子状态.
修改全局变量
- if(子状态满足约束条件)
- {
- dfs(子状态)
- }
恢复全局变量 // 回溯部分
- }
- }
来源: http://www.bubuko.com/infodetail-2947038.html