一：解题思路
这个题目的解题关键有2点：1.任何时候写下左括号都是合法的。2.只有写下的左括号多于右括号的时候，再写下右括号才合法。
Time:O(4^n/n*sqrt(n)),Space:O(n)
二：完整代码示例 (C++版和Java版)
C++:
class Solution { public: void generate(vector<string>& result, string str, int left, int right) { if (left == 0 && right == 0) { result.push_back(str); } else { if (left > 0) generate(result,str+‘(‘,left-1,right); if (right > left) generate(result,str+‘)‘,left,right-1); } } vector<string> generateParenthesis(int n) { vector<string> result; if (n <= 0) return result; generate(result,"",n,n); return result; } };
Java:
class Solution { private void generate(List<String> result,String str,int left,int right) { if(left==0 && right==0) { result.add(str); } else { if(left>0) generate(result,str+‘(‘,left-1,right); if(right>left) generate(result,str+‘)‘,left,right-1); } } public List<String> generateParenthesis(int n) { if(n<=0) return new ArrayList<>(); List<String> result=new ArrayList<>(); generate(result,"",n,n); return result; } }
原文：https://www.cnblogs.com/repinkply/p/12642576.html