正确的括号方式可以有几种。斯特灵数嘛
dp[i] = 连加 (k=0..i-1)dp[k]*dp[i-1-k]
意思是最后一个括号括前 k 个括号可以组成的个数与剩下的括号可以组成的个数的乘积的和。
#include&string&
class Solution {
vector&string& p[2000];
bool used[2000];
void gen(int x)
if(used[x])
for(int i=0;i&x;i++)
for(int j=0;j&p[i].size();j++)
string res=&(&+p[i][j]+&)&;
for(int k=0;k&p[x-1-i].size();k++)
string t=res+p[x-1-i][k];
p[x].push_back(t);
used[x]=1;
vector&string& generateParenthesis(int n) {
for(int i=0;i&2000;i++)
used[i]=0;
used[0]=1;
p[0].push_back(&&);
return p[n];
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：34362次
积分：2029
积分：2029
排名：第10196名
原创：175篇
转载：17篇
评论：15条
(1)(1)(3)(2)(10)(7)(11)(5)(68)(39)(23)(12)(10)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:
&((()))&, &(()())&, &(())()&, &()(())&, &()()()&
自然而然地相当递归。不知有没有非递归的解法，简单查了一下网上也都是这种解法。
【Java代码】
public class Solution {
private List&String& list = new ArrayList&String&();
public List&String& generateParenthesis(int n) {
run(&&, n, 0);
// l 为剩余左括号数，r为剩余未匹配的右括号数目
public void run(String str, int l, int r) {
if (l == 0 && r == 0) {
list.add(str);
if (l & 0) {
String s = str + &(&;
run(s, l-1, r+1);
if (r & 0) {
String s = str + &)&;
run(s, l, r-1);
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：176989次
积分：3123
积分：3123
排名：第5486名
原创：126篇
转载：14篇
评论：89条
文章：96篇
阅读：91686
(1)(3)(4)(17)(4)(4)(25)(15)(19)(7)(9)(3)(4)(6)(4)(2)(16)1335人阅读
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:
&((()))&, &(()())&, &(())()&, &()(())&, &()()()&
原创地址：
此题给人一看就是眼花缭乱的感觉。在纷繁的特征中总结出来规律还真是非常难的。
网上分析实在太少了，令人难以看明白。
所以我在这里分析一下，觉得我分析得不好，或者深度不够的，请多多指教。
以我的思维，我是使用二叉树的思维思考这个算法的，不过最后没能自己成功的写出程序。查了查LeetCode论坛，使用的是递归算法，感觉真是精妙绝伦！因为我考虑这个递归树的时候有两个难点：
1 如何两边同时遍历一棵树？
2 如何剔除不适合的路径？比如最中间的路径是不满足条件的。
到底是什么样的树？构造出这样的概念树，我觉得就好理解很多了。
看看下面我画的树：
顺着路径对称地，比如最左边和最右边，遍历两个路径，就是一个解，除了最中间的不符合要求。所以要遍历这样的概念树，很困难。
下面是程序出处：
vector&string& generateParenthesis(int n) {
vector&string&
if (n&0) generator(ans, &&, 0, 0, n);
void generator(vector&string& & ans, string s, int l, int r, int n) { // r/l: appearance of ) (
if (l == n) {
ans.push_back(s.append(n-r, ')'));
generator(ans, s+'(', l+1, r, n);
if (l&r) generator(ans, s+&)&, l, r+1, n);
逐句看看吧，反正没多少。
if (l == n) {
ans.push_back(s.append(n-r, ')'));
这个功能是已经遍历了左边的树，然后这里并不需要遍历右边的树，而是非常巧妙地直接补上右括号“）”就完事了。没做过的话，真是想破头脑都难想出来。
而这样居然神奇地完成一个解了。
generator(ans, s+'(', l+1, r, n);
这句就是遍历左递归树，是先序遍历哦，有人说理解为后序，不对，应该是先序。因为s+'('就是先把&(&加进去了，然后到下一层树节点。
左子树递归遍历完了就开始右子树递归遍历：
if (l&r) generator(ans, s+&)&, l, r+1, n);
右子树都是“）”右括号的，所以s+&)&代表遍历右子树。
不过令人头痛的就是怎么理解if(l&r)这个条件？
看了些博客说理解为不能让右括号多于左括号，有一定道理，那为什么前面遍历左子树的时候，就是填写左括号“（”的时候，不添加一个判断左子树不能大于右子树的条件呢？所以这样理解好像不大合理。
我的理解，这句正是剔除中间不符合条件的路径的巧妙句子。
因为只有左子树的最右边的子树才会可能出现右括号&)&大于左括号&(&的情况的，所以这个条件真是&黄娟! 幼妇! 外孙&！
&递归回溯法的程序，其实题目并不难，上面的分析我重新看看，使用树的思维分析也可以，不过如果熟悉了，那么还是不需要分析的太麻烦，不过这样分析对思维锻炼很有好处。
本题最难的就是一个条件判断啦，如我重新写了个程序，如下。这个条件就是if （left & right），这是个十分难想出来的条件，最后怎么吃透这个条件呢？
我就是使用实例，反复走几遍，然后就确立了这个条件，这就是根据实例观察其中的规律的能力了。
虽然就是那么一个条件，自己摸索出来，难度还是相当大的。所以本题我觉得因人而异才能确定其难度指数，我觉得相对难度应该达到4.5星级了，不注意的话，面试的时候是很难写出正确的程序的。也许写个差不多的程序是可以的，不过所谓的差不多程序，就是差一点点没正确的程序，说到底就是错误的程序。
&class Solution {
vector&string& generateParenthesis(int n)
vector&string&
genParenthesis(rs, s, n, n);
void genParenthesis(vector&string& &rs, string &s, int left, int right)
if (left==0)
rs.push_back(s);
rs.back().append(right, ')');
s.push_back('(');
genParenthesis(rs, s, left-1, right);
s.pop_back();
if (left & right)
s.push_back(')');
genParenthesis(rs, s, left, right-1);
s.pop_back();
&难度指数： 4.5星级
版权声明：本文作者靖心，靖空间地址：http://blog.csdn.net/kenden23/，未经本作者允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：780832次
积分：16213
积分：16213
排名：第271名
原创：737篇
转载：13篇
译文：16篇
评论：262条
文章：192篇
阅读：326813
(2)(3)(1)(1)(13)(11)(11)(6)(67)(74)(79)(110)(88)(25)(17)(41)(70)(98)(45)(3)(1)[LeetCode]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即可。注意：放括号的过程中，永远不能出现当前右括号的数量大于左括号数量的情况
public class Solution {
public static ArrayList generateParenthesis(int n) {
ArrayList list = new ArrayList();
StringBuilder str = new StringBuilder();
if (n == 0) {
recursive(0, 0, n, str, list);
public static void recursive(int left, int right, int n, StringBuilder str, ArrayList list) {
if (left < right) {
if (left == n && right == n) {
String tmp = str.toString();
list.add(tmp);
if (left < n) {
StringBuilder newstr = new StringBuilder(str.toString());
newstr.append('(');
recursive(left + 1, right, n, newstr, list);
if (right < n) {
StringBuilder newstr = new StringBuilder(str.toString());
newstr.append(')');
recursive(left, right + 1, n, newstr, list);
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。【Generate Parentheses】cpp - 承续缘 - 博客园
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
class Solution {
vector&string& generateParenthesis(int n)
vector&string&
vector&char&
Solution::dfs(ret, tmp, 0, n, n, n);
static void dfs( vector&string&& ret, vector&char&& tmp, int sum, int left, int right, int n )
if ( left==0 && right==0 )
ret.push_back(string(tmp.begin(),tmp.end()));
// '(' or ')'
if ( left&0 )
tmp.push_back('(');
Solution::dfs(ret, tmp, sum+1, left-1, right, n);
tmp.pop_back();
if ( right&0 && sum&0 )
tmp.push_back(')');
Solution::dfs(ret, tmp, sum-1, left, right-1, n);
tmp.pop_back();
第一反应是不是stack相关的解法，因为感觉跟逆波兰表达式差不多。
后来发现用&深搜+剪枝&即可解决。
这里left表示没有使用的'('，right表示没有使用的')'；sum标记使用left和right的情况，使用一次left给sum加1，使用一次right给sum减1。
能迭代下去的核心条件是：使用的sum必须大于等于0.
1. 深搜情况，这里每层有两个分支：'(' 或者 ')'
2. 剪枝条件:
　　a)&只要使用过'('小于n, 则可以加到tmp中
　　b) 使用过的')'小于n, 并且当前的sum是大于0的
=======================================
第二次用dfs过这道题，套路稍微熟悉一些了，考虑dfs的分支顺序：每一层可以加入left括号也可以加入right括号，终止条件的是剩余的left括号数量一定小于right括号的数量。
随笔 - 253}