LEET code -- 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:

"((()))", "(()())", "(())()", "()(())", "()()()"



下面利用Backtracking的方式  我現在選擇( 後面的選擇丟給下一個recursive來決定
leftsize代表有多少(   這個數目不能超過n
rightsize代表有多少)   這個數目不能超過(


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> ans; string s="("; findparent(ans,s,1,0,n); return ans; } void findparent(vector<string> &ans, string s,int leftsize,int rightsize,int n){//left is ( right is ) if(n*2==leftsize+rightsize){ ans.push_back(s); return; } if(leftsize<n)findparent(ans,s+"(",leftsize+1,rightsize,n); if(rightsize<leftsize)findparent(ans,s+")",leftsize,rightsize+1,n); } };



-----------------------








-------------------------

神人iterater

logic here is simple:
First, store a result vector, then for every entry:

• add '(', when cannot add ')'
• add ')', when cannot add '('
• copy this entry and add '(' and ')' separately to original and new copy, when both are valid

here count and countleft are vectors that store check values.




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> result(1); vector<int> count(1,0),countleft(1,0); for(int i=0;i<2*n;++i){ int m=count.size(); for(int j=0;j<m;++j){ if(count[j]==0){ result[j]+='('; count[j]++; countleft[j]++; } else if(countleft[j]==n) result[j]+=')'; else{ result.push_back(result[j]+')'); count.push_back(count[j]-1); countleft.push_back(countleft[j]); result[j]+='('; count[j]++; countleft[j]++; } } } return result; } };