回溯法
括号生成
http://www.nowcoder.com/questionTerminal/c9addb265cdf4cdd92c092c655d164ca
为了防止出现右括号在左括号前面的情况发生，每次递归一定要先考虑左括号，当左括号的情况考虑完了，再考虑右括号，而且要保证每次递归时已有的右括号的数量不能大于左括号的数量，否则也会造成交叉。
public ArrayList<String> generateParenthesis (int n) {
if (n == 0){
return new ArrayList<>();
}
ArrayList<String> list = new ArrayList<>();
backTrace("",0,0,n,list);
return list;
}
private void backTrace(String cur,int left_num,int right_num,int n,ArrayList<String> list){
if (cur.length() == n * 2){
list.add(cur);
return;
}
if (left_num < n ){
backTrace(cur + "(",left_num + 1,right_num,n,list);
}
if (right_num < left_num){
backTrace(cur + ")",left_num,right_num + 1,n,list);
}
}
查看5道真题和解析
