本文共 4845 字，大约阅读时间需要 16 分钟。
回溯法的基本思想就是
试探，按照优选条件去向前搜索，以达到目标。
但是在搜索到某一步时，发现原先这样并不能满足条件，就回退一步重新选择，这种走不通就退回再走的技术成为回溯法。
在做回溯法的题目的时候，有添加状态或元素就一定有与之对应的回退状态和元素。若是寻找成功，回退以查看有没有其他满足条件的解；如果寻找不成功，回退以查看其它情况。
例题： 从1，... ，n中取出k个数，要求不重复。
1、先写个框架，包含了main函数用于测试代码，一个方法fromnpickk，这个时候，fromnpickk方法还没有返回值
package com.company;import java.util.ArrayList;import java.util.List;public class fromnpickk { public static void main(String[] args){ fromnpickk test = new fromnpickk(); System.out.print(test.fromnpickk(5,2)); } public List > fromnpickk(int n, int k) { }}
2、定义一个返回值，应该是双层列表，再定义一个临时变量，用于记录每次找到一个解
package com.company;import java.util.ArrayList;import java.util.List;public class fromnpickk { public static void main(String[] args){ fromnpickk test = new fromnpickk(); System.out.print(test.fromnpickk(5,2)); } public List > fromnpickk(int n, int k) { List > result = new ArrayList<>(); List list = new ArrayList<>(); // 临时变量，一个符合条件的解 return result; }}
3、新建一个回溯函数的形式，以迭代调用，这个回溯函数需要哪些值呢？
n代表总数n， k代表还要取出多少个数，start代表起始取数位置，result表示所有的结果， list用来保存已知的解。
package com.company;import java.util.ArrayList;import java.util.List;public class fromnpickk { public static void main(String[] args){ fromnpickk test = new fromnpickk(); System.out.print(test.fromnpickk(5,2)); } public List > fromnpickk(int n, int k) { List > result = new ArrayList<>(); List list = new ArrayList<>(); // 临时变量，一个符合条件的解 backtrack(n,k,1,result, list); // 回溯函数 return result; } public void backtrack(int n,int k, int start, List > result ,List list){ }}
目前为止，你有一点java基础，就和我一样菜都能看的懂，Go on
4、写一下backtrack的处理逻辑，如果k<0就停止，k表示还要挑几个，如果k<0那么自然就停止
package com.company;import java.util.ArrayList;import java.util.List;public class fromnpickk { public static void main(String[] args){ fromnpickk test = new fromnpickk(); System.out.print(test.fromnpickk(5,2)); } public List > fromnpickk(int n, int k) { List > result = new ArrayList<>(); List list = new ArrayList<>(); // 临时变量，一个符合条件的解 backtrack(n,k,1,result, list); // 回溯函数 return result; } public void backtrack(int n,int k, int start, List > result ,List list){ if (k < 0) return; }}
如果k==0，那么此时说明我们找到了一个合格的解，需要把list加入到最后的解的集合中去
package com.company;import java.util.ArrayList;import java.util.List;public class fromnpickk { public static void main(String[] args){ fromnpickk test = new fromnpickk(); System.out.print(test.fromnpickk(5,2)); } public List > fromnpickk(int n, int k) { List > result = new ArrayList<>(); List list = new ArrayList<>(); // 临时变量，一个符合条件的解 backtrack(n,k,1,result,list); // 回溯函数 return result; } public void backtrack(int n,int k, int start, List > result ,List list){ if (k < 0) return; else if (k == 0){ result.add(new ArrayList<>(list)); } }}
从n个数中，先挑一个，一般从第一个挑起，然后调用回溯函数，再挑k-1个，每次需要更新start的值，因为挑过的数就不能重复了，list.remove(list.size()-1);他的作用就是每次清除一个空位 让后续元素加入。寻找成功，最后一个元素要退位，寻找不到，方法不可行，那么我们回退，也要移除最后一个元素
package com.company;import java.util.ArrayList;import java.util.List;public class fromnpickk { public static void main(String[] args){ fromnpickk test = new fromnpickk(); System.out.print(test.fromnpickk(5,2)); } public List > fromnpickk(int n, int k) { List > result = new ArrayList<>(); List list = new ArrayList<>(); // 临时变量，一个符合条件的解 backtrack(n,k,1,result,list); // 回溯函数 return result; } public void backtrack(int n,int k, int start, List > result ,List list){ if (k < 0) return; else if (k == 0){ result.add(new ArrayList<>(list)); }else { for (int i = start;i <= n; i++){ list.add(i); // 添加元素 backtrack(n,k-1,i+1,result,list); list.remove(list.size()-1); // 回退 } } }}
假设n=3，k=2，
此时第一次的backtrack应该是backtrack(3,2,1,[[]],[])，记为B1，由于k=2，所以进入for循环，i=1,2,3，当i=1时list = [1]，
backtrack(3,1,2,[[]],[1])，记为B2，又进入了backtrack，此时的k=1，又进入for循环，i=2,3，当i=2时，list = [1,2]，此时又进入了backtrack
backtrack(3,0,3,[[]],[1,2])，记为B3，由于这个时候k=0，所以，result = [[1,2]]，此时B3执行完毕，B2还没执行完毕，回过去执行B2，执行list回退，list = [1]，此时for循环的第一遍结束，第二遍开始，i=3，list = [1,3]，
进入backtrack，backtrack(3,0,4,[[]],[1,3])，记为B4，此时k=0，所以，result = [[1,2],[1,3]]，此时B4执行完毕，回过去执行B2的第二个for循环，执行list回退，list = [1]，此时for循环结束，list = [1]，此时回去执行B1，list回退，list=[]，进入for循环，i=2，依次类推
转载地址：http://gejvi.baihongyu.com/