本文共 1715 字,大约阅读时间需要 5 分钟。
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:"((()))", "(()())", "(())()", "()(())", "()()()"
简单的回溯:
bool isCurPaOk(char *tmp,int i,int n){ int left = 0,right = 0; for(int j=0;j<=i;j++) { if(tmp[j]=='(') { left++; } else { right++; } } if(right>left || left > n) { return false; } else { return true; } } void genePa(int i,int n,char** ret,int*returnSize,char *tmp){ if(i==2*n - 1) { tmp[i]=')';tmp[2*n]='\0'; char *col=(char*)malloc((2*n+1)*sizeof(char)); memcpy(col,tmp,(2*n+1)*sizeof(char)); // if(*returnSize > n*n - 1) // { // ret=realloc(ret,n*n*n*sizeof(char*)); // } ret[*returnSize]=col; (*returnSize)++; return; } tmp[i]='('; if(isCurPaOk(tmp,i,n)) { genePa(i+1,n,ret,returnSize,tmp); } tmp[i]=')'; if(isCurPaOk(tmp,i,n)) { genePa(i+1,n,ret,returnSize,tmp); } }char** generateParenthesis(int n, int* returnSize) { *returnSize = 0; char** ret = (char**)malloc(n*n*n*n*sizeof(char*)); char *tmp=(char*)malloc((2*n+1)*sizeof(char)); tmp[0]='('; genePa(1,n,ret,returnSize,tmp); return ret;}每增加一个都要重新判断.
卡特兰数 代表了一系列问题:Catalan数的定义令h(1)=1,Catalan数满足递归式:h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1),n>=2该递推关系的解为:h(n) = C(2n-2,n-1)/n,n=1,2,3,...(其中C(2n-2,n-1)表示2n-2个中取n-1个的组合数)
转:http://blog.csdn.net/hackbuteer1/article/details/7450250 介绍了很多题目
http://blog.csdn.net/yutianzuijin/article/details/13161721 有个很好的解决方法