参考： https://blog.csdn.net/vers encoder/article/details/52071930
3359 blog.csdn.net/vers encoder/article/details/52072350
(手式)回溯是指搜索法，按照实现目标的优选条件进行前瞻性搜索。
但是，检索到某个步骤时，发现这样就不满足条件，后退一步重新选择，如果不顺利就后退的技术就是回溯法。
制作回溯法主题时，只要有添加状态和要素，就一定有相应的回溯状态和要素。 如果检索成功，则返回并确认是否有其他符合条件的解。 如果搜索失败，请回滚以查看其他情况。
例题： 1，从n中取出k个，要求不重复。
n=4，k=2，1，21，31，42，32，43，4
主题框架：
很容易先构建所有变量{ publiclistlistintegercombine (intn，int k ) }
publiclistlistintegerresult=new ArrayList (； 然后，可以创建新的递归函数形式，并重复调用。
backtracking(intn，int k，int start，ListInteger list )，其中n为总数n，k取出多少个，start用于保存开始位置，list用于保存已知解。
这些一定会被使用的吧。 然后我们来看看具体的回溯函数：
publiclistlistintegerresult=new ArrayList (； publiclistlistintegercombine (intn，int k ) ) { ListInteger list=new ArrayList； 反向跟踪(n，k，1，list )； 返回结果； }公共void back tracking (intn，int k，int start，ListInteger list ) if(K0 ) { return； }elseif(k==0) result.add (new ArrayList ) list )； }else{for(intI=start； i=n； I ) ) list.add ) I； //添加元素backtracking(n，k-1，i 1，list )； list.remove(list.size ) (-1 )； //后退} }具体思路：
1 .要在1.n=4、k=2、1、2、3、4中选择两个数字，请尝试如下。 除了先选1之外，你只需要再选一个数字。 此时，请注意k=1。 (此时，只需选择一个数字。 当然，也可以先选择2、3或4，使之通俗化。 可以选择(1-n )中的所有数字。 这个可以用一个周期来描述吗？ 每次选择参加我们的链表list的一个，下次就选择k-1个数字。 那个什么时候结束？ 当然是k0的时候。 这个时候都选完了。
2 .添加了作为I起点的start变量。 你为什么要参加那个？ 例如，我们第一次加入1，下次搜索时能再搜索1吗？ 绝对不行啊！ 我们必须从他的下一个数字，即2、3或4开始。 所以start开始标记这个很重要。
3 .添加： list.remove(list.size ) (-1 )； 他的作用是每次清除一个空位，增加后续元素。 检索成功了。 最后一个要素必须下台。 如果找不到，方法不可能的话，我们必须撤退，最后的要素也要删除。
给出手形变形(1，2，3 )的排列，给出所有组合方法)、1，2，3，12，13，23，123。
同样可以用回溯法解决。 寻求组合有助于暴力求解，用于列举所有可能的结果，并逐一判断。
publicarraylistarraylistintegercombine (int [ ] nums ) arraylistarraylistintegerresult=new ArrayList )； arraylistintegerlist=new ArrayList (； 巴克tr
acing(result,list,0,nums); return result; } public void backtracing(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,int start, int[] nums){ result.add(new ArrayList<>(list)); for (int i = start; i < nums.length; i++) { list.add(nums[i]); backtracing(result,list,i+1,nums); list.remove(list.size()-1); } }进阶式：
分割字符串：
给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果
样例：给一个字符串"123"
返回[["1","2","3"],["12","3"],["1","23"]]
分析：我们可以设置一个起始位置start，每次我们都从start位置开始向后划分一个或者两个字符出去，这样就有很多种划分路径，当一种路径走到末端的时候，之前划分出去的需要回退以再次以不同形式划分。
public static List<List<String>> result = new ArrayList<>(); // 首先新建一个 result public static List<List<String>> splitString(String s) { List<String> list = new ArrayList<>(); backtraceing(s, 0, list); // 回溯函数 return result; } public static void backtraceing(String s, int start, List<String> list){ // start标注每次的起始位置 if(start>s.length()){ return; }else if(start==s.length()){ result.add(new ArrayList<>(list)); }else{ for (int i = start; i<start+2 && i < s.length(); i++) { // i<start+2： 每次划分一个或者两个字符 String subString = s.substring(start,i+1); list.add(subString); backtraceing(s,i+1,list); list.remove(list.size()-1); } } }高阶式：
例：矩阵中的路径
题目描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。 public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { }}思路：1. 在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的
第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
2. 找下一个节点时，可能是刚刚搜索过的位置，所以需要新建一个visited数组记录下一个节点是否被访问过。
参考代码：
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { if(matrix==null || matrix.length==0 || str==null || str.length==0 || rows<=0 || cols<=0 || rows*cols < str.length){ return false; } boolean[] visited = new boolean[rows*cols]; char[] path = null; int start = 0; //表示str的起始位置 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if(isbacktracing(matrix, i, j, rows, cols, str, visited, start)){ // 从第i，j个位置是否能走通 return true; } } } return false; } public boolean isbacktracing(char[] matrix,int i, int j,int rows,int cols,char[] str,boolean[] visited,int start){ if(start >= str.length){ return true; }else { int index = i*cols + j; // 记录当前访问的节点 if(i<0 || i>=rows || j<0 || j>=cols || matrix[index] != str[start] || visited[index]==true){ //判断是否合适或者是否已被访问 return false; } visited[index] = true; // 标记已读 boolean judge = isbacktracing(matrix,i+1,j,rows,cols,str,visited,start+1)|| isbacktracing(matrix,i,j+1,rows,cols,str,visited,start+1)|| isbacktracing(matrix,i-1,j,rows,cols,str,visited,start+1)|| isbacktracing(matrix,i,j-1,rows,cols,str,visited,start+1); if(judge){ return true; } visited[index] = false; // 回退 return false; // 搜索不到，返回false } }