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时，就可以放置新的左括号。当右括号出现次数小于左括号出现次数时，就可以放置新的右括号。

 

1 public class Solution { 2     public ArrayList
     
       generateParenthesis(int n) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         ArrayList
      
        result = new ArrayList
       
        (); 6         if(n != 0){ 7             generate(result, "", 0, 0, 0, n); 8         }         9         return result;10     }11     12     public void generate(ArrayList
        
          result, String tmp, int deep, int left, int right, int n){13         if(deep == 2 * n){14             result.add(tmp);15             return;16         }17         18         if(left < n){19             tmp += "(";20             generate(result, tmp, deep + 1, left + 1, right, n);21             tmp = tmp.substring(0, tmp.length() - 1);22         }23         24         if(right < left){25             tmp += ")";26             generate(result, tmp, deep + 1, left, right + 1, n);27             tmp = tmp.substring(0, tmp.length() - 1);28         }29         30     }31 }