思路：n表示有n个"("和n个")"；第一个可以为"("，第二个可以为"("或者")",当第二个为"("，第三个可以为"("或者”)“，如果第二个为")"，第三个不能为")"；。。。所有情况列出来，就是一棵树。具体到某一层的时候我们其实是可以判断这层符不符合要求（即括号组合是否有效），如果不符合要求就可以不用往下一层走，直接回到上一层往下（另一个分支走），这就是回溯法

三个要素：出口，递归函数定义（参数，记录数据，可以用于当前层的判断，中间值的存储），处理逻辑（判断，什么情况可以往下走）

@Test
public void test() {List<String> list = generateParenthesis(3);System.out.println(Arrays.toString(list.toArray()));
}//使用回溯法
public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();generate(0, 0, 0, "", n, result);return result;
}/*** 生成n对有效的括号，结果存储在result中* @param left 已经用了几个左括号* @param right 已经用了几个右括号* @param level 现在在第几层* @param saveStr 存储中间值（中间状态）* @param n 生成n对有效括号* @param result 存储符合条件的结果*/
private void generate(int left, int right, int level, String saveStr, int n, List<String> result) {if(level == 2*n) {result.add(saveStr);}//还可以加左括号if(left<n) {generate(left+1, right, level+1, saveStr+"(", n, result);}//还可以加右括号if(left>right) {generate(left, right+1, level+1, saveStr+")", n, result);}
}