首页 > 代码库 > Generate Parentheses（组合，回溯）
Generate Parentheses（组合，回溯）
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
暴力思路：其实就是组合，n=3，则有6个位置，每个位置可以插入‘(‘，或者‘)‘，当n=3时，就有64中可能，只需对每一种可能作必要的筛选即可。
代码：
class Solution {private: char parenthesis[2]; vector<string> res; int num;public: void dfs(int dep,string temp){ if(dep==num){ stack<char> s; for (int i=0;i<temp.size();++i) { if(s.empty()) s.push(temp[i]); else if(!s.empty()&&temp[i]==‘)‘){ if(s.top()==‘(‘) s.pop(); }else{ s.push(temp[i]); } } if(!s.empty()) return; res.push_back(temp); return; } for (int i=0;i<2;++i) { temp.push_back(parenthesis[i]); dfs(dep+1,temp); temp.pop_back(); } return; } vector<string> generateParenthesis(int n) { parenthesis[0]=‘(‘; parenthesis[1]=‘)‘; num=n*2; string temp=""; dfs(0,temp); return res; }};
Generate Parentheses（组合，回溯）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。