解法一：（回溯法）用两个整数记录左右括号数，以在回溯过程中保证先生成左括号，且左右括号数不能大于n。

class Solution {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<String>();StringBuffer temp = new StringBuffer();int left = 0, right = 0; // 用于标记目前左右括号的数目backtrace(n, result, temp, left, right);return result;}public void backtrace(int n, List result, StringBuffer temp, int left, int right){if(left==n && right==n){result.add(temp.toString());return;}if(right>n || left>n){return;}if(left>right){// 左括号数大于右括号数，左右括号都能加for(int i=0; i<2; i++){if(i==0){// 加左括号temp.append('(');backtrace(n, result, temp, left+1, right);temp.deleteCharAt(temp.length()-1);  // 不是temp.deleteAt(temp.size()-1);}else{// 加右括号temp.append(')');backtrace(n, result, temp, left, right+1);temp.deleteCharAt(temp.length()-1);}}}else{// 左括号数<=右括号数，只能加左括号temp.append('(');backtrace(n, result, temp, left+1, right);temp.deleteCharAt(temp.length()-1);}}
}

注意：

• 要避免左右括号的数目大于指定的数目，不添加如下判断会导致一直回溯 -> 内存溢出：if(right>n || left>n){return;}
• temp.deleteCharAt(temp.length()-1)而不是temp.deleteAt(temp.size()-1)
• StringBuffer转String的方法：
  • result.add(temp.toString())
  • result.add(new String(temp))