回溯就是暴力枚举,只不过对于有些问题,能够写出来已经很不错了,例如50个for循环的嵌套,代码中肯定不能写50个for,而是通过递归来完成。回溯虽然是暴力枚举,但是可以通过剪枝优化,具体优化在回溯树上看。
回溯解决的问题有:组合、切割、子集、排列、n皇后
回溯问题都能构造成一个回溯树,解决回溯问题,一定要画回溯树;并且有固定的代码编写模板。
public void backtracking(参数) {
if (终?条件) {
存放结果;
return;
}
for(选择:本层集合中元素(树中节点孩?的数量就是集合的??)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
回溯方法的难点在于参数的设置、回溯方法中for循环的编写。
组合:对于单个集合的组合(如77. 组合),要设置startIndex,用来记录本层递归的中,集合从哪里开始遍历(集合就是[1,…,n])每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex,简单来说,startIndex控制的是单集合横向变量问题。对于多个集合的组合(如17. 电话号码的字母组合),不用设置startIndex,for从0开始,但也要有一个index记录遍历第几个数字了,index是记录遍历第几个数字了。