描述

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 { public: vector<string> generateParenthesis(int n) { vector<string> result; string s = ""; parenthesis(n, n, s, result); return result; } void parenthesis(int left_count, int right_count,string s, vector<string>& result){ if(right_count == 0 && left_count == 0){ result.push_back(s); return; } if(left_count >0){ parenthesis(left_count-1, right_count, s+'(', result); } if(right_count > left_count){ parenthesis(left_count, right_count-1, s+')', result); } } };

结果

他山之玉

C++ O(n) solutioin

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res(1, "("); vector<int> left(1, 1); int l=2*n; for(int i=1; i<l; i++) { for(int j=res.size()-1; j>=0; j--) { if(left[j]>0) { if(left[j]<l-i) { res.emplace_back(res[j]+"("); left.push_back(left[j]+1); } res[j]+=")"; left[j]--; } else { res[j]+="("; left[j]++; } } } return res; } };

这个思路没有利用递归求，而是写了一个vector记录左括号的次数，利用循环来做，很有意思。

Java O(n) solution

public List<String> generateParenthesis(int n) { List<String> list = new ArrayList<String>(); backtrack(list, "", 0, 0, n); return list; } public void backtrack(List<String> list, String str, int open, int close, int max){ if(str.length() == max*2){ list.add(str); return; } if(open < max) backtrack(list, str+"(", open+1, close, max); if(close < open) backtrack(list, str+")", open, close+1, max); }

也是利用递归，只是编程方法而已。

python O(n) solution

def generateParenthesis(self, n): def generate(p, left, right, parens=[]): if left: generate(p + '(', left-1, right) if right > left: generate(p + ')', left, right-1) if not right: parens += p, return parens return generate('', n, n) def generateParenthesis(self, n, left=0, right=0, cur=''): if left == n: return [cur + ')' * (n - right)] if left == right: return self.generateParenthesis(n, left + 1, right, cur + '(') return self.generateParenthesis(n, left + 1, right, cur + '(') \ + self.generateParenthesis(n, left, right + 1, cur + ')')