1、算法基础

1、定义

简单的说，回溯算法就是一种结合递归的暴力搜索方法

2、适用问题

回溯算法 - 图1

3、算法思想

回溯算法 - 图2
伪代码：

  • 回溯函数遍历过程

    1. for(选择：本层集合中元素（苏中节点的数量就是集合的大小）){
    2.   处理几点；
    3.   backtracking（路径，选择列表）; //递归
    4.   回溯，撤销处理结果
    5. }

  • 回溯算法模板框架 ```java void backtracking(参数){ if(终止条件）{ 存放条件； return； }

    for(选择：本层集合中元素（苏中节点的数量就是集合的大小）){ 处理几点； backtracking（路径，选择列表）; //递归 回溯，撤销处理结果 } }

  2. <a name="lzasm"></a>
  3. # 2、组合问题
  4. > 首先画一个树形来模拟组合问题
  5. > 确定需要有一个递增的起始参数
  6. > 三部曲
  8. ```java
  9.     ArrayList<List<Integer>> res = new ArrayList<>();
  10.     LinkedList<Integer> path = new LinkedList<>();
  11.     public List<List<Integer>> combine(int n, int k) {
  12.         //从 start=1 开始
  13.         trackCombine(n,k,1);
  14.         return res;
  15.     }
  17.     //确定参数：前两个和原函数一致，start表示for循环中递归调用的起始位置
  18.     void trackCombine(int n, int k,int start) {
  19.         //终止条件
  20.         if (path.size() == k) {
  21.             res.add(new ArrayList<>(path)); //此处path是全局变量，所以需要重新创建
  22.             return;
  23.         }
  24.         //for循环
  25.         for (int i = start; i <= n; i++){
  26.             path.add(i); //数字加入数组
  27.             trackCombine(n, k, ++start);
  28.             path.removeLast(); //回溯，返回上一级
  29.         }
  30.     }

3、组和总和

套用模板

  • 原始

    1. class Solution {
    2.   ArrayList<List<Integer>> resSum3 = new ArrayList<>();
    3.   LinkedList<Integer> paths = new LinkedList();
    4.   public List<List<Integer>> combinationSum3(int k, int n) {
    5.       trackSum3(k, n, 1);
    6.       return resSum3;
    8.   }
    10.   void trackSum3(int k, int n, int start) {
    11.       int sum = 0;
    12.       if (paths.size() == k) {
    13.           for (int i = 0; i < paths.size(); i++) {
    14.               sum += paths.get(i);
    15.           }
    16.           if (sum==n) resSum3.add(new ArrayList<>(paths));
    17.       }
    18.       for (int i = start; i < 10; i++) {
    19.           paths.add(i);
    20.           trackSum3(k, n, ++start);
    21.           paths.removeLast();
    22.       }
    23.   }
    24. }

  • 将求和带入到参数中

    1. class Solution {
    2.   ArrayList<List<Integer>> resSum3 = new ArrayList<>();
    3.   LinkedList<Integer> paths = new LinkedList();
    4.   public List<List<Integer>> combinationSum3(int k, int n) {
    5.       trackSum3(k, n, 1,0);
    6.       return resSum3;
    8.   }
    10.   void trackSum3(int k, int n, int start,int sum) {
    11.       //将sum带入 时间复杂度会增高
    12.       if (paths.size() == k) {
    13.           if (sum==n) resSum3.add(new ArrayList<>(paths));
    14.       }
    15.       for (int i = start; i < 10; i++) {
    16.           sum += i;
    17.           paths.add(i);
    18.           trackSum3(k, n, ++start, sum);
    19.           sum -= i;
    20.           paths.removeLast();
    21.       }
    22.   }
    23. }

  • 剪枝

    1. class Solution {
    3.   ArrayList<List<Integer>> resSum3 = new ArrayList<>();
    4.   LinkedList<Integer> paths = new LinkedList();
    5.   public List<List<Integer>> combinationSum3(int k, int n) {
    6.       trackSum3(k, n, 1,0);
    7.       return resSum3;
    9.   }
    11.   void trackSum3(int k, int n, int start,int sum) {
    12.       //初步剪枝，如果求和过程中大于目标则返回
    13.       if (sum > n) {
    14.           return;
    15.       }
    16.       if (paths.size() == k) {
    17.           if (sum==n) resSum3.add(new ArrayList<>(paths));
    18.           return;
    19.       }
    20.       //二次剪枝，如果构不成k个数，则返回
    21.       for (int i = start; i <= 9 - (k - paths.size()) + 1; i++) {
    22.           sum += i;
    23.           paths.add(i);
    24.           trackSum3(k, n, i+1, sum);
    25.           sum -= i;
    26.           paths.removeLast();
    27.       }
    28.   }
    29. }

4、电话号码的字母组和

  1. class Solution {
  2.     ArrayList<String> res = new ArrayList<>();
  3.     public List<String> letterCombinations(String digits) {
  4.           if (digits.isEmpty()) return res;
  5.         String[] strMap = new String[]{ "","","abc","def","ghi","jkl","mno","pqrs","tuv",  "wxyz"};
  6.         trackLetter(digits, strMap, 0);
  7.         return res;
  8.     }
  10.     StringBuffer sb = new StringBuffer();
  12.     //此处的num不是记录开始位置，而是为了记录结果集中当前处理的下标
  13.     void trackLetter(String digits, String[] strMap, int num) {
  14.         if (num== digits.length()) {
  15.             res.add(sb.toString());
  16.             return;
  17.         }
  18.         String str = strMap[digits.charAt(num)-'0'];
  19.         //遍历str
  20.         for (int i = 0; i < str.length(); i++) {
  21.             sb.append(str.charAt(i));
  22.             trackLetter(digits, strMap, num+1);
  23.             sb.deleteCharAt(sb.length() - 1);
  24.         }
  26.     }
  27. }

5、组和总和||

此题的难点，主要是数字可以重复使用 对于此，有以下方式应对：

  • 将数组排序，从小到大，保证数字递加时不会提前跳出循环
  • 在回溯模板中，for循环增加 如果sum大于target时，跳出循环
  • for 中的下标 i ，作为下次循环的起始值
  1.     ArrayList<List<Integer>> ressum = new ArrayList<>();
  2.     LinkedList<Integer> path = new LinkedList<>();
  3.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  4.         if (candidates.length == 0) {
  5.             return ressum;
  6.         }
  7.         //数组先行排序
  8.         Arrays.sort(candidates);
  9.         trackSum(candidates, target, 0,0);
  10.         return ressum;
  11.     }
  13.     void trackSum(int[] cand, int target,int sum, int start) {
  14.         System.out.println("sum："+sum);
  15.         if (sum == target){
  16.             ressum.add(new ArrayList<>(path));
  17.             return;
  18.         }
  20.         for (int i = start; i < cand.length; i++) {
  21.             //由于这种相加的方式，是可以重复的添加，因此需要添加此条件跳出循环
  22.             if (sum + cand[i] > target) break;
  23.             System.out.println(i);
  24.             path.add(cand[i]);
  25.             //将i 作为下次开始，保证数字的重复使用
  26.             trackSum(cand, target, sum + cand[i], i);
  27.             path.removeLast();
  28.         }
  29.     }

6、分割回文串

  1. 回溯函数的参数：
    1. 字符串，索引值
  2. 回溯函数的逻辑：
    1. 如果子字符串为回文字符串，则将结果加到path中
    2. 如果不是回文，则跳过本次for循环
    3. 递归调用下一个索引起点（索引++）
    4. path移除末尾元素进行回溯
  3. 终止条件
    1. 如果索引值大于等于s 的长度，则返回
  1. class Solution {
  2.     ArrayList<List<String >> resP = new ArrayList<>();
  3.     LinkedList<String> pathp = new LinkedList<>();
  4.     public List<List<String>> partition(String s) {
  5.         if (s.length()==0) return resP;
  6.         tracePart(s, 0);
  7.         return resP;
  8.     }
  10.     void tracePart(String s, int index) {
  11.                 // System.out.println("index: "+index);
  12.         if (index >= s.length()) {
  13.             resP.add(new ArrayList<>(pathp));
  14.             return;
  15.         }
  16.         for (int i = index; i < s.length(); i++) {
  17.             if (partFlag(s, index, i)) {
  18.                 //此处的i+1|只是为了截取字符串
  19.                 pathp.add(s.substring(index, i+1));
  20.             } else {
  21.                 //当不是回文时，跳过本次循环
  22.                 continue;
  23.             }
  24.             //当遍历字符是回文时，在本次的基础上索引直接加1（不需要再减回来），遍历下一个字符
  25.             tracePart(s,i+1);
  26.             //路径变量进行回溯
  27.             pathp.removeLast();
  28.         }
  29.     }
  31.      boolean partFlag(String s, int start, int end) {
  32.         for (int i = start, j = end; i < j; i++, j--) {
  33.             if (s.charAt(i) != s.charAt(j)) {
  34.                 return false;
  35.             }
  36.         }
  37.         return true;
  38.     }
  39. }

7、复原IP地址

image.png 复原IP地址本质上还是数字组和问题，只不过不能改变数字的顺序，变的只是切割的位置，而且每一个 被分割的子字符串都要符合IP地址的条件。 按照以上思路，我们可以预先定义一个路径集和结果集。 在回溯模板中，参数设置为字符串和开始索引 终止条件就是路径集的大小为 4 ，并且如果开始索引的大小和s的长度一致时，将路径集通过join的方法加入到结果集中。 for循环中i = start，由于字串大小限制最大为3，所以可以增加条件 i<start+3 与 i<s.length() 如果子字符串不符合ip条件。直接跳出循环否则进行回溯 在isValid函数中，s.length()!=1 对单“0”的优化

  1. class Solution {
  2.     ArrayList<String> resIP = new ArrayList<>();
  3.     LinkedList<String> pathIP = new LinkedList<>();
  4.     public List<String> restoreIpAddresses(String s) {
  5.         if (s.length() == 0) {
  6.             return resIP;
  7.         }
  8.         trackIP(s, 0);
  9.         return resIP;
  10.     }
  12.     void trackIP(String s, int start) {
  13.         //如果存入的数字总共有四个
  14.         if (pathIP.size() == 4) {
  15.             //且构成的数字和原字符串一致 
  16.             if (start == s.length()) {
  17.                 //数组用join方法加标点
  18.                 resIP.add(String.join(".", pathIP));
  19.             }
  20.             return;
  21.         }
  22.         //因为IP是由三个数字组成，且不能超过字符串长度限制
  23.         for (int i = start; i < start + 3 && i < s.length(); i++) {
  24.             //System.out.println("start:" + start);
  25.             // System.out.println("i:" + i);
  26.             String sub = s.substring(start, i+1);
  27.             //如果不符合要求，可以直接跳出递归
  28.             if (!isValid(sub)) break;
  29.             //将字串加入路径中
  30.             pathIP.add(sub);
  31.             trackIP(s, i + 1);
  32.             //回溯
  33.             pathIP.removeLast();
  34.         }
  35.     }
  37.     boolean isValid(String s) {
  38.         //s.length()!=1 对单“0”的优化
  39.         if (s.length()!=1&&s.charAt(0)=='0' || Integer.valueOf(s)>255) {
  40.             return false;
  41.         }
  42.         return true;
  43.     }
  44. }

8、子集问题

与组和、排列不同，如果将这些都抽象成一棵树的话，组和和分割是收集树的叶子节点，而子集是收集树的所有节点。 又因为子集都是无序的，所以回溯时，for循环要从start开始，并且每一层递归的结果都需要收集。 终止条件是当前长度等于s.length

  1. class Solution {
  2.     ArrayList<List<Integer>> resSub = new ArrayList<>();
  3.     LinkedList<Integer> pathSub = new LinkedList<>();
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         if (nums.length==0) return resSub;
  6.         trackSub(nums, 0);
  7.         return resSub;
  8.     }
  9.     void trackSub(int[] nums,int start) {
  10.         resSub.add(new ArrayList<>(pathSub));
  11.         if (start==nums.length) return;
  12.         for (int i = start; i < nums.length; i++) {
  13.             pathSub.add(nums[i]);
  14.             trackSub(nums, i + 1);
  15.             pathSub.removeLast();
  16.         }
  17.     }
  18. }

9、子集问题2

思想和 8 类似，还是收集回溯树的路径信息，主要有以下两点变动

  1. 有序数组无序且重复，因此需要先对数组进行排序
  2. 为了防止子集重复问题，在for中如果相邻两个数重复则直接跳过
  1.     ArrayList<List<Integer>> resSub = new ArrayList<>();
  2.     LinkedList<Integer> pathSub = new LinkedList<>();
  4.     void trackSub(int[] nums,int start) {
  5.         resSub.add(new ArrayList<>(pathSub));
  6.         if (start==nums.length) {
  7.             System.out.println("changdu ");
  8.             return;
  9.         }
  10.         for (int i = start; i < nums.length; i++) {
  11.             //相邻两个数字重复则跳过
  12.             if (i>start && nums[i]==nums[i-1]) continue;
  13.             pathSub.add(nums[i]);
  14.             trackSub(nums, i + 1);
  15.             pathSub.removeLast();
  16.         }
  18.     }
  19.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  20.         if (nums.length==0) return resSub;
  21.         //将数组排序
  22.         Arrays.sort(nums);
  23.         trackSub(nums, 0);
  24.         return resSub;
  25.     }

10、递增子序列

与子集问题类似，都是收集抽象树上的路径，但是这个数组不是组和问题，所以不能直接排序，因此需要利用一个hash，将数字的使用情况收集起来

  • 利用hashmap ```java class Solution { ArrayList> resSeq = new ArrayList<>(); LinkedList pathSeq = new LinkedList<>(); public List> findSubsequences(int[] nums) {

    1.   if (nums.length==0) return resSeq;
    2.   trackSeq(nums,0);
    3.   return resSeq;

    }

    void trackSeq(int[] nums, int start) {

    1.   if (pathSeq.size()>1) resSeq.add(new ArrayList<>(pathSeq));
    2.   if (start== nums.length) return;
    4.   //录本层元素是否重复使⽤，新的⼀层uset都会重新定义（清空）
    5.   HashMap<Integer, Integer> map = new HashMap<>();
    7.   for (int i = start; i < nums.length; i++) {
    8.       if (!pathSeq.isEmpty()&&nums[i] < pathSeq.getLast()){ continue;}
    9.       if (map.getOrDefault(nums[i],0)>0) continue;
    11.       map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    13.       pathSeq.add(nums[i]);
    14.       trackSeq(nums, i + 1);
    15.       pathSeq.removeLast();
    16.   }

    }

}

  2. - 利用hashset
  3. ```java
  4. class Solution {
  5.     //存放结果
  6.     List<List<Integer>> result = new ArrayList<>();
  7.     //暂存结果
  8.     List<Integer> path = new ArrayList<>();
  10.     public List<List<Integer>> findSubsequences(int[] nums) {
  11.         backTrack(nums, 0);
  12.         return result;
  13.     }
  15.     private void backTrack(int[] nums, int startIndex) {
  16.         if(path.size() > 1){
  17.             result.add(new ArrayList<>(path));//注意这⾥不要加return，因为要取树上的所有节点
  18.         }
  19.         HashSet<Integer> uset = new HashSet<>();//录本层元素是否重复使⽤，新的⼀层uset都会重新定义（清空）
  20.         for (int i = startIndex; i < nums.length; i++) {
  21.             //!path.isEmpty()&&nums[i]<path.get(path.size()-1)) : 保证子序列是递增的
  22.             //!uset.add(nums[i]) ：保证在同一层不会重复使用相同数字
  23.             if ((!path.isEmpty()&&nums[i]<path.get(path.size()-1))||!uset.add(nums[i])) {
  24.                 continue;
  25.             }
  26.             path.add(nums[i]);
  27.             backTrack(nums, i + 1);
  28.             path.remove(path.size() - 1);
  29.         }
  30.     }
  31. }

11、全排列

全排可以想象成一种暴力排列的方式，因此不需要有前后顺序，所以for循环中的索引每次都从0 开始，参数也无需有索引开始的取值，但由于每次都从0 开始，所以需要判断每层的递归树中使用次数

  • 辅助数组

    1. class Solution {
    2.   ArrayList<List<Integer>> resPer = new ArrayList<>();
    3.   LinkedList<Integer> pathPer = new LinkedList<>();
    4.   boolean[] visited;
    5.   public List<List<Integer>> permute(int[] nums) {
    6.       visited = new boolean[nums.length];
    7.       tackPermute(nums);
    8.       return resPer;
    9.   }
    11.   void tackPermute(int[] nums) {
    12.       if (pathPer.size() == nums.length) {
    13.           resPer.add(new ArrayList<>(pathPer));
    14.           return;
    15.       }
    17.       for (int j = 0; j < nums.length; j++) {
    18.           if (visited[j]) {
    19.               continue;
    20.           }
    21.           visited[j] = true;
    22.           pathPer.add(nums[j]);
    23.           tackPermute(nums);
    24.           pathPer.removeLast();
    25.           visited[j] = false;
    26.       }
    27.   }
    28. }

  • 直接判断path中是否含有这个数字

    1. class Solution {
    2.   ArrayList<List<Integer>> resPer = new ArrayList<>();
    3.   LinkedList<Integer> pathPer = new LinkedList<>();
    4.   public List<List<Integer>> permute(int[] nums) {
    5.       tackPermute(nums);
    6.       return resPer;
    8.   }
    10.   void tackPermute(int[] nums) {
    11.       if (pathPer.size() == nums.length) {
    12.           resPer.add(new ArrayList<>(pathPer));
    13.           return;
    14.       }
    16.       for (int j = 0; j < nums.length; j++) {
    17.           if (pathPer.contains(nums[j])) {
    18.               continue;
    19.           }
    20.           pathPer.add(nums[j]);
    21.           tackPermute(nums);
    22.           pathPer.removeLast();
    23.       }
    24.   }
    25. }

    12、全排列2

    大致思路：由于题目中的数组可以重复，但是结果不能有重复的排列，主要思路和组合问题2 类似，都是先将数组排序，然后在for 循环中控制数字添加到路径中。 具体：经分析，此题应是树的层级去重，因此在前后判断的同时还需加一个控制位，来对递归层数相同的排列去重，否则直接横向、纵向都会被去重。具体参考下图： image.png

  1. public class Day_02 {
  2.     ArrayList<List<Integer>> resPer = new ArrayList<>();
  3.     LinkedList<Integer> pathPer = new LinkedList<>();
  4.     boolean[] uset;
  5.     public List<List<Integer>> permuteUnique(int[] nums) {
  6.         uset = new boolean[nums.length];
  7.         Arrays.sort(nums);
  8.         trackPer(nums);
  9.         return resPer;
  10.     }
  12.     void trackPer(int[] nums) {
  13.         if (nums.length == pathPer.size()) {
  14.             resPer.add(new ArrayList<>(pathPer));
  15.         }
  16.         for (int i = 0; i < nums.length; i++) {
  17.             if (uset[i]) continue;
  18.             //通过uset[i - 1] 进行横向去重
  19.             //当条件为true ，也能AC，但是由于这样是纵向去重的，所以复杂度会更高
  20.             if (i != 0 && nums[i] == nums[i - 1] && uset[i - 1]==false) {
  21.                 continue;
  22.             }
  23.             //去重后对标记位赋值，可以视为加锁
  24.             uset[i] = true;
  25.             pathPer.add(nums[i]);
  26.             trackPer(nums);
  27.             pathPer.removeLast();
  28.             uset[i] = false;}}}

【同层剪枝 VS 非同层剪枝】 相信你现在已经知道如下条件的作用了，很多人对最后一个子条件比较疑惑。即采用!visited[i - 1] 或 visited[i - 1]，结果竟然是一样的，不光都是对的，而且输出也是一摸一样。

  1. if(visited[i] || (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1])) continue;

实际上如果你愿意付出点时间用纸笔跟踪一下递归过程，你会发现 !visited[i - 1] 实现了 「同层剪枝」，而 visited[i - 1] 实现「非同层剪枝」。 【同层剪枝】 当选取到nums[i]，并满足 i > 0 && nums[i - 1] == nums[i] 时，若 !visited[i - 1] = true，说明以nums[i - 1]为某一层元素的选择已穷尽，以至于在回溯的时候置 visited[i - 1] = false）。于是后续会根据这个条件跳过同层相等元素。 【非同层剪枝】 最后一个子条件若采用 visited[i - 1]，当选取到nums[i]，并满足 i > 0 && nums[i - 1] == nums[i] 时，若 visited[i - 1] = true，表明当前是在nums[i - 1]的子树中选择nums[i]，根据这个条件，在子树中遇到nums[i]，总是不选取（continue），那么该子树总是无法提供有效排列（因为缺少nums[i]），于是对该子树的搜索都是无效的。之后回溯到nums[i - 1]所在层后，由于撤销为 visited[i - 1] = false，不再满足visited[i - 1] = true，于是不会跳过，可以正常选取到包含nums[i - 1]和nums[i]的排列。 通过上述说明，采用!visited[i - 1]的「同层剪枝」效率更高，因为「非同层剪枝」对nums[i - 1]的子树（存在nums[i] == nums[i - 1]）的搜索是无效的。 另外我们也可以看到，无论哪一种，输出有效排列的顺序是一致的。二者的差别可理解为，非同层剪枝比同层剪枝多做了无效子树搜索动作。

13、N皇后问题

N皇后主要难点在于这个是二维的问题，打破这个障碍，思路就变得通顺了，无非就是一行代表递归的层数，n+1代表递归层数+1，然后在访问到点时，校验这个点是否符合N皇后的规则 image.png

  1. class Solution {
  2.     List<List<String>> res = new ArrayList<>();
  4.     public List<List<String>> solveNQueens(int n) {
  5.         char[][] chessboard = new char[n][n];
  6.         for (char[] c : chessboard) {
  7.             Arrays.fill(c, '.');
  8.         }
  9.         backTrack(n, 0, chessboard);
  10.         return res;
  11.     }
  14.     public void backTrack(int n, int row, char[][] chessboard) {
  15.         if (row == n) {
  16.             res.add(Array2List(chessboard));
  17.             return;
  18.         }
  20.         for (int col = 0;col < n; ++col) {
  21.             if (isValid (row, col, n, chessboard)) {
  22.                 chessboard[row][col] = 'Q';
  23.                 backTrack(n, row+1, chessboard);
  24.                 chessboard[row][col] = '.';
  25.             }
  26.         }
  28.     }
  31.     public List Array2List(char[][] chessboard) {
  32.         List<String> list = new ArrayList<>();
  34.         for (char[] c : chessboard) {
  35.             list.add(String.copyValueOf(c));
  36.         }
  37.         return list;
  38.     }
  41.     public boolean isValid(int row, int col, int n, char[][] chessboard) {
  42.         // 检查列
  43.         for (int i=0; i<row; ++i) { // 相当于剪枝
  44.             if (chessboard[i][col] == 'Q') {
  45.                 return false;
  46.             }
  47.         }
  49.         // 检查45度对角线
  50.         for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
  51.             if (chessboard[i][j] == 'Q') {
  52.                 return false;
  53.             }
  54.         }
  56.         // 检查135度对角线
  57.         for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
  58.             if (chessboard[i][j] == 'Q') {
  59.                 return false;
  60.             }
  61.         }
  62.         return true;
  63.     }
  64. }