[leetcode] 22. Generate Parentheses

[leetcode] 22. Generate Parentheses

Description

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对括号，然后输出其所有的组合方式。

这是一个深度优先搜索的题目，注意left代表剩余的左括号，right表示剩余的右括号；在任意时刻，左括号数目要大于右括号数目。

1）left大于right（left和right分别表示剩余左右括号的个数），即，临时变量中右括号的数大于左括号的数，则说明出现了“)(”，这是非法情况，返回即可；

2）left和right都等于0说明，临时变量中左右括号数相等，所以将临时变量中的值存入res中；

3）其余的情况是，先放左括号，然后放右括号，然后递归。注意参数的更新。

代码

class Solution {public: vector generateParenthesis(int n) { vector result; DFS(n,n,"",result); return result; } void DFS(int left,int right,string res,vector &result){ if(left>right){ return; } if(left==0&&right==0){ result.push_back(res); }else{ if(left>0){ DFS(left-1,right,res+"(",result); } if(right>0){ DFS(left,right-1,res+")",result); } } }};

参考文献

​​[Leetcode] generate parentheses 生成括号​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。