• 以下均来源：【代码随想录】

    理论基础

    【来源：代码随想录】

  • 什么是回溯法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式，回溯是递归的副产品，只要有递归就会有回溯。

  • 回溯法的效率
    • 并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案
  • 回溯法解决的问题
    • 组合问题：N个数里面按一定规则找出k个数的集合
    • 切割问题：一个字符串按一定规则有几种切割方式
    • 子集问题：一个N个数的集合里有多少符合条件的子集
    • 排列问题：N个数按一定规则全排列，有几种排列方式
    • 棋盘问题：N皇后，解数独等等
  • 如何理解回溯法
    • 回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，就构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
  • 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
如图：
image.png
注意图中，我特意举例集合大小和孩子的数量是相等的！
回溯函数遍历过程伪代码如下：

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

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

1.组合问题

把组合问题抽象为如下树形结构：
image.png
可以看出这个棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现n相当于树的宽度，k相当于树的深度。
那么如何在这个树上遍历，然后收集到我们要的结果集呢？
图中每次搜索到了叶子节点，我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合

  1.  private List<List<Integer>> ans = new ArrayList<>();
  3. public List<List<Integer>> combine(int n, int k) {
  4.     List<Integer> path = new ArrayList<>();
  5.     process(n, k, 1, path);
  6.     return ans;
  7. }
  10. private void process(int n, int k, int index, List<Integer> path) {
  11.     if (path.size() == k) {
  12.         List<Integer> list = new ArrayList<>(path);
  13.         ans.add(list);
  14.         return;
  15.     }
  17.     for (int i = index; i <= n ; i++) {
  18.         path.add(i);
  19.         process(n, k, i + 1, path);
  20.         path.remove(path.size() - 1);
  21.     }
  22. }

剪枝优化

这个遍历的范围是可以剪枝优化的，怎么优化呢？
来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。
这么说有点抽象，如图所示：
image.png
图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
注意代码中i，就是for循环里选择的起始位置。

  1. for (int i = index; i <= n ; i++)

接下来看一下优化过程如下：

  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]

  1. for (int i = index; i <= n - (k - path.size()) + 1 ; i++) { // 剪枝优化

2.组合总和Ⅲ

  • 无非就是相比77.组合多了一个限制而已 ```java private List> ans = new ArrayList<>(); private LinkedList path = new LinkedList<>();

public List> combinationSum3(int k, int n) { process(n, k, 1, 0); return ans; }

private void process(int targetSum, int k, int index, int sum) { //剪枝 if (sum > targetSum) return;

  1. if (path.size() == k) {
  2.     if (sum == targetSum) {
  3.         ans.add(new ArrayList<>(path));
  4.     }
  5.     return;
  6. }
  8. for (int i = index; i <= 9 - (k - path.size()) + 1; i++) { //剪枝
  9.     path.add(i);
  10.     sum += i;
  11.     process(targetSum, k, i + 1, sum);
  12.     path.removeLast();  // 回溯
  13.     sum -= i;  // 回溯
  15. }

}

  4. <a name="AKuGH"></a>
  5. # 3.[电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
  7. - 需要一个映射
  8. ```java
  9.      char[][] map = {
  10.             {' ', ' ', ' '},
  11.             {' ', ' ', ' '},
  12.             {'a', 'b', 'c'},
  13.             {'d', 'e', 'f'},
  14.             {'g', 'h', 'i'},
  15.             {'j', 'k', 'l'},
  16.             {'m', 'n', 'o'},
  17.             {'p', 'q', 'r', 's'},
  18.             {'t', 'u', 'v'},
  19.             {'w', 'x', 'y', 'z'}
  20.     };
  22.     List<String> ans = new ArrayList<>();
  24.     public List<String> letterCombinations(String digits) {
  25.         if (digits == null || digits.length() == 0) {
  26.             return ans;
  27.         }
  28.         char[] str = digits.toCharArray();
  29.         LinkedList<Character> path = new LinkedList<>();
  30.         process(str, 0, path);
  31.         return ans;
  32.     }
  34.     private void process(char[] str, int index, LinkedList<Character> path) {
  35.         if (index == str.length) {
  36.             StringBuilder sb = new StringBuilder();
  37.             for (char s : path) {
  38.                 sb.append(s);
  39.             }
  40.             ans.add(sb.toString());
  41.             return;
  42.         }
  44.         char[] letters = map[str[index] - '0'];
  45.         for (int i = 0; i < letters.length; i++) {
  46.             path.add(letters[i]);
  47.             process(str, index + 1, path);
  48.             path.removeLast();
  49.         }
  51.     }

4.组合总和⭐

  • candidate 中的每个元素都 互不相同

  • candidates 中的 同一个 数字可以 无限制重复被选取 

    1.    private List<List<Integer>> ans = new ArrayList<>();
    2.   private List<Integer> path = new ArrayList<>();
    4.   public List<List<Integer>> combinationSum(int[] candidates, int target) {
    5.       process(candidates, 0, target);
    6.       return ans;
    7.   }
    9.   // arr[index....]的数自由选择，每一种数任意个，（0 .。。。 index -1） 不用管
    10.   // 凑出targetLeave
    11.   private void process(int[] candidates, int index, int targetLeave) {
    12.       if (targetLeave == 0) {
    13.           ans.add(new ArrayList<>(path));
    14.           return;
    15.       }
    17.       if (targetLeave < 0) {
    18.           return;
    19.       }
    21.       for (int i = index; i < candidates.length; i++) {
    22.           path.add(candidates[i]);
    23.           targetLeave -= candidates[i];
    24.           process(candidates, i, targetLeave);  // 关键点:不用i+1了，表示可以重复读取当前的数
    25.           targetLeave += candidates[i];  // 回溯
    26.           path.remove(path.size() - 1);  // 回溯
    27.       }
    28.   }

剪枝优化

  • 对原数组进行排序

  • 如果已经遍历到的i使得targetLeave - candidates[i] < 0就不用再继续遍历了

    1. private List<List<Integer>> ans = new ArrayList<>();
    2.   private List<Integer> path = new ArrayList<>();
    4.   public List<List<Integer>> combinationSum(int[] candidates, int target) {
    5.       Arrays.sort(candidates);
    6.       process(candidates, 0, target);
    7.       return ans;
    8.   }
    10.   // arr[index....]的数自由选择，每一种数任意个，（0 .。。。 index -1） 不用管
    11.   // 凑出targetLeave
    12.   private void process(int[] candidates, int index, int targetLeave) {
    13.       if (targetLeave == 0) {
    14.           ans.add(new ArrayList<>(path));
    15.           return;
    16.       }
    17. //
    18. //        if (targetLeave < 0) {
    19. //            return;
    20. //        }
    22.       for (int i = index; i < candidates.length && targetLeave - candidates[i] >= 0; i++) {  // 剪枝优化
    23.           path.add(candidates[i]);
    24.           targetLeave -= candidates[i];
    25.           process(candidates, i, targetLeave);  // 关键点:不用i+1了，表示可以重复读取当前的数
    26.           targetLeave += candidates[i];  // 回溯
    27.           path.remove(path.size() - 1);  // 回溯
    28.       }
    29.   }

5.组合总和Ⅱ⭐

这道题目和39.组合总和(opens new window)如下区别：

  1. 本题candidates 中的每个数字在每个组合中只能使用一次。
  2. 本题数组candidates的元素是有重复的，而39.组合总和(opens new window)是无重复元素的数组candidates

最后本题和39.组合总和(opens new window)要求一样，解集不能包含重复的组合。
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

如何在搜索的过程中去掉重复组合？
所谓去重，其实就是使用过的元素不能重复选取
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！
选择过程树形结构如图所示：
image.png

  • 单层搜索的逻辑

这里与39.组合总和(opens new window)最大的不同就是要去重了。
前面我们提到：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。
如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。
此时for循环里就应该做continue的操作。
这块比较抽象，如图：
image.png
我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

  • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  • used[i - 1] == false，说明同一树层candidates[i - 1]使用过 ```java private List> ans = new ArrayList<>(); private List path = new ArrayList<>();
  1. public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  2.     Arrays.sort(candidates);
  3.     boolean[] flag = new boolean[candidates.length];
  4.     process(candidates, 0, target, flag);
  5.     return ans;
  6. }
  8. private void process(int[] candidates, int index, int targetLeave, boolean[] flag) {
  9.     if (targetLeave == 0) {
  10.         ans.add(new ArrayList<>(path));
  11.     }
  13.     for (int i = index; i < candidates.length && targetLeave - candidates[i] >= 0; i++) {
  14.         // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  15.         // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  16.         // 要对同一树层使用过的元素进行跳过
  17.         if (i > 0 && candidates[i] == candidates[i - 1] && !flag[i - 1]) {
  18.             continue;
  19.         }
  20.         path.add(candidates[i]);
  21.         targetLeave -= candidates[i];
  22.         flag[i] = true;
  23.         process(candidates, i + 1, targetLeave, flag); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
  24.         flag[i] = false;
  25.         targetLeave += candidates[i];
  26.         path.remove(path.size() - 1);
  27.     }
  28. }
  2. - 直接使用index进行去重也可以
  3. ```java
  4.   List<List<Integer>> res = new ArrayList<>();
  5.   LinkedList<Integer> path = new LinkedList<>();
  6.   int sum = 0;
  8.   public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
  9.     //为了将重复的数字都放到一起，所以先进行排序
  10.     Arrays.sort( candidates );
  11.     backTracking( candidates, target, 0 );
  12.     return res;
  13.   }
  15.   private void backTracking( int[] candidates, int target, int start ) {
  16.     if ( sum == target ) {
  17.       res.add( new ArrayList<>( path ) );
  18.       return;
  19.     }
  20.     for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
  21.       //正确剔除重复解的办法
  22.       //跳过同一树层使用过的元素
  23.       if ( i > start && candidates[i] == candidates[i - 1] ) {
  24.         continue;
  25.       }
  27.       sum += candidates[i];
  28.       path.add( candidates[i] );
  29.       // i+1 代表当前组内元素只选取一次
  30.       backTracking( candidates, target, i + 1 );
  32.       int temp = path.getLast();
  33.       sum -= temp;
  34.       path.removeLast();
  35.     }
  36.   }

6.分割回文串⭐

本题这涉及到两个关键问题：

  1. 切割问题，有不同的切割方式
  2. 判断回文

其实切割问题类似组合问题。

例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…..。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…..。

所以切割问题，也可以抽象为一棵树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

Stri ， L~R范围上能分解出多少种
截图_20224329074316.png

  1.     List<List<String>> ans = new ArrayList<>();
  2.     LinkedList<String> path = new LinkedList<>(); // 放已经回文的子串
  4.     public List<List<String>> partition(String s) {
  5.         process(s, 0);
  6.         return ans;
  7.     }
  9.     private void process(String str, int index) {
  10.         // 如果起始位置已经等于s的大小，说明已经找到了一组分割方案了
  11.         if (index == str.length()) {
  12.             ans.add(new ArrayList<>(path));
  13.             return;
  14.         }
  16.         for (int i = index; i < str.length(); i++) {
  17.             if (isPalindrome(str, index, i)) {// 是回文子串
  18.                 // 获取[index,i]在s中的子串
  19.                 path.add(str.substring(index, i + 1));
  20.             } else {// 不是回文，跳过
  21.                 continue;
  22.             }
  23.             process(str, i + 1);// 寻找i+1为起始位置的子串
  24.             path.removeLast();// 回溯过程，弹出本次已经填在的子串
  25.         }
  26.     }
  28.     private boolean isPalindrome(String str, int start, int end) {
  29.         while (start < end) {
  30.             if (str.charAt(start) != str.charAt(end)) {
  31.                 return false;
  32.             }
  33.             start++;
  34.             end--;
  35.         }
  36.         return true;
  37.     }

注意切割过的位置，不能重复切割，所以，process(s, i + 1); 传入下一层的起始位置为i + 1。

7.复原IP地址

这其实也是一个切割问题

切割问题就可以使用回溯搜索法把所有可能性搜出来

切割问题可以抽象为树型结构，如图：

截图_20223829093812.png

  • 递归参数

    • Index一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
    • 本题我们还需要一个变量pointNum，记录添加逗点的数量。

  • 递归终止条件
    终止条件和131.分割回文串 (opens new window)情况就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
    pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。
    然后验证一下第四段是否合法，如果合法就加入到结果集里 

    2.  List<String> ans = new ArrayList<>();
    4.  public List<String> restoreIpAddresses(String s) {
    5.      if (s.length() > 12 || s.length() == 0 ) {
    6.          return ans;
    7.      }
    8.      process(s, 0, 0);
    9.      return ans;
    10.  }
    12.  private void process(String s, int index, int pointNum) {
    13.      if (pointNum == 3) {
    14.          if (isValid(s, index, s.length() - 1)) {
    15.              ans.add(s);
    16.          }
    17.          return;
    18.      }
    20.      for (int i = index; i < s.length(); i++) {
    21.          //s[index, i]
    22.          if (isValid(s, index, i)) {
    23.              s = s.substring(0, i + 1) + "." + s.substring(i + 1);
    24.              pointNum++;
    25.              process(s, i + 2, pointNum);
    26.              pointNum--;
    27.              s = s.substring(0, i + 1) + s.substring(i + 2);
    28.          } else {
    29.              break;
    30.          }
    31.      }
    32.  }
    34.  //判断字符串[start, end]区间是否合法
    35.  private boolean isValid(String str, int start, int end) {
    36.      if (start > end) {
    37.          return false;
    38.      }
    39.      //前导0
    40.      if (str.charAt(start) == '0' && start != end) {
    41.          return false;
    42.      }
    43.      //超范围
    44.      int sum = 0;
    45.      for (int i = start; i <= end; i++) {
    46.          if (str.charAt(i) < '0' || str.charAt(i) > '9') {
    47.              return false;
    48.          }
    49.          sum = sum * 10 + (str.charAt(i) - '0'); //注意别忘了 - ‘0’
    50.          if (sum > 255) {
    51.              return false;
    52.          }
    53.      }
    54.      return true;
    55.  }

8.子集问题⭐

求子集问题和77.组合(opens new window)和131.分割回文串(opens new window)又不一样了。
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
有同学问了，什么时候for可以从0开始呢？
求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。
以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：
image.png
从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

  1.      List<List<Integer>> ans = new ArrayList<>();
  2.     LinkedList<Integer> path = new LinkedList<>();
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         if (nums == null) {
  6.             return ans;
  7.         }
  8.         process(nums, 0);
  9.         return ans;
  10.     }
  12.     private void process(int[] nums, int index) {
  13.         ans.add(new ArrayList<>(path));
  14.         if (index >= nums.length) {
  15.             return;
  16.         }
  17.         for (int i = index; i < nums.length; i++) {
  18.             path.add(nums[i]);
  19.             process(nums, i + 1);
  20.             path.removeLast();
  21.         }
  22.     }

9.子集Ⅱ⭐

这道题目和78.子集 (opens new window)区别就是集合里有重复元素了，而且求取的子集要去重。
用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）
image.png
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

  1. List<List<Integer>> ans = new ArrayList<>();
  2.     LinkedList<Integer> path = new LinkedList<>();
  5.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  6.         boolean[] used = new boolean[nums.length];
  7.         if (nums == null) {
  8.             return ans;
  9.         }
  10.         Arrays.sort(nums);// 去重需要排序
  11.         process(nums, 0, used);
  12.         return ans;
  13.     }
  15.     private void process(int[] nums, int index, boolean[] used) {
  16.         ans.add(new ArrayList<>(path));
  17.         if (index >= nums.length) {
  18.             return;
  19.         }
  20.         for (int i = index; i < nums.length; i++) {
  21.             // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  22.             // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  23.             // 而我们要对同一树层使用过的元素进行跳过
  24.             if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {
  25.                 continue;
  26.             }
  28.             path.add(nums[i]);
  29.             used[i] = true;
  30.             process(nums, i + 1, used);
  31.             used[i] = false;
  32.             path.removeLast();
  33.         }
  34.     }

补充

本题也可以不使用used数组来去重，因为递归的时候下一个Index是i+1而不是0

  1. List<List<Integer>> ans = new ArrayList<>();
  2.     LinkedList<Integer> path = new LinkedList<>();
  5.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  6.         boolean[] used = new boolean[nums.length];
  7.         if (nums == null) {
  8.             return ans;
  9.         }
  10.         Arrays.sort(nums);// 去重需要排序
  11.         process(nums, 0, used);
  12.         return ans;
  13.     }
  15.     private void process(int[] nums, int index, boolean[] used) {
  16.         ans.add(new ArrayList<>(path));
  17.         if (index >= nums.length) {
  18.             return;
  19.         }
  20.         for (int i = index; i < nums.length; i++) {
  21.             // 而我们要对同一树层使用过的元素进行跳过
  22.             if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex
  23.                 continue;
  24.             }
  26.             path.add(nums[i]);
  27.             used[i] = true;
  28.             process(nums, i + 1, used);
  29.             used[i] = false;
  30.             path.removeLast();
  31.         }
  32.     }

10.递增子序列⭐

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。

这又是子集，又是去重，是不是不由自主的想起了刚刚讲过的90.子集II (opens new window)。

就是因为太像了，更要注意差别所在，要不就掉坑里了！

在90.子集II (opens new window)中我们是通过排序，再加一个标记数组来达到去重的目的。

而本题求自增子序列，是不能对原数组经行排序的，排完序的数组都是自增子序列了。

所以不能使用之前的去重逻辑！

本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。

为了有鲜明的对比，我用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：

回溯算法专题 - 图10
回溯三部曲

  • 递归函数参数

本题求子序列，很明显一个元素不能重复使用，所以需要startIndex，调整下一层递归的起始位置。

代码如下：

  1. List<List<Integer>> ans = new ArrayList<>();
  2. LinkedList<Integer> path = new LinkedList<>();
  4. private void process(int[] nums, int index)
  • 终止条件

本题其实类似求子集问题，也是要遍历树形结构找每一个节点，所以和回溯算法：求子集问题！ (opens new window)一样，可以不加终止条件，startIndex每次都会加1，并不会无限递归。

但本题收集结果有所不同，题目要求递增子序列大小至少为2，所以代码如下：

  1.    if (path.size() >= 2) {
  2.        ans.add(new ArrayList<>(path));
  3.        // 注意这里不要加return，因为要取树上的所有节点
  4.    }
  • 单层搜索逻辑

回溯算法专题 - 图11
在图中可以看出，同一父节点下的同层上使用过的元素就不能在使用了

那么单层搜索代码如下：

  1.  Set<Integer> set = new HashSet<>(); // 使用set对本层元素进行去重
  3. for (int i = index; i < nums.length; i++) {
  4.     if (!path.isEmpty() && nums[i] < path.peekLast() || set.contains(nums[i])) {
  5.         continue;
  6.     }
  7.     set.add(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
  8.     path.add(nums[i]);
  9.     process(nums, i + 1);
  10.     path.removeLast();
  11. }

对于已经习惯写回溯的同学，看到递归函数上面的**uset.insert(nums[i]);**，下面却没有对应的pop之类的操作，应该很不习惯吧，哈哈

这也是需要注意的点，**unordered_set<int> uset;** 是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！

  • 总代码

    2.    List<List<Integer>> ans = new ArrayList<>();
    3.    LinkedList<Integer> path = new LinkedList<>();
    5.   public List<List<Integer>> findSubsequences(int[] nums) {
    6.       if (nums == null) {
    7.           return ans;
    8.       }
    10.       process(nums, 0);
    11.       return ans;
    12.   }
    14.   private void process(int[] nums, int index) {
    15.       if (path.size() >= 2) {
    16.           ans.add(new ArrayList<>(path));
    17.           // 注意这里不要加return，因为要取树上的所有节点
    18.       }
    20.       Set<Integer> set = new HashSet<>(); // 使用set对本层元素进行去重
    22.       for (int i = index; i < nums.length; i++) {
    23.           if (!path.isEmpty() && nums[i] < path.peekLast() || set.contains(nums[i])) {
    24.               continue;
    25.           }
    26.           set.add(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
    27.           path.add(nums[i]);
    28.           process(nums, i + 1);
    29.           path.removeLast();
    30.       }
    31.   }

11.全排列⭐

我以[1,2,3]为例，抽象成树形结构如下：
回溯算法专题 - 图12
回溯三部曲

  • 递归函数参数

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。
但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:
回溯算法专题 - 图13
代码如下：

  1. List<List<Integer>> ans = new ArrayList<>();
  2. LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> permute(int[] nums)
  • 递归终止条件

image.png
可以看出叶子节点，就是收割结果的地方。
那么什么时候，算是到达叶子节点呢？
当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。
代码如下：

  1. // 此时说明找到了一组
  2. if (path.size() == nums.length) {
  3.     ans.add(new ArrayList<>(path));
  4.     return;
  5. }
  • 单层搜索的逻辑

这里和77.组合问题 (opens new window)、131.切割问题 (opens new window)和78.子集问题 (opens new window)最大的不同就是for循环里不用startIndex了。
因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。
而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
代码如下：

  1. for (int i = 0; i < nums.length; i++) {
  2.     if (used[i]) {
  3.         continue;
  4.     }
  5.     path.add(nums[i]);
  6.     used[i] = true;
  7.     process(nums, used);
  8.     used[i] = false;
  9.     path.removeLast();
  10. }

整体java代码如下：

  1. private List<List<Integer>> ans = new ArrayList<>();
  2. private LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> permute(int[] nums) {
  5.     boolean[] used = new boolean[nums.length];
  7.     process(nums, used);
  8.     return ans;
  9. }
  11. //nums中无重复数字
  12. private void process(int[] nums, boolean[] used ) {
  13.     if (path.size() == nums.length) {
  14.         ans.add(new ArrayList<>(path));
  15.         return;
  16.     }
  18.     for (int i = 0; i < nums.length; i++) {
  19.         if (used[i]) {
  20.             continue;
  21.         }
  22.         path.add(nums[i]);
  23.         used[i] = true;
  24.         process(nums, used);
  25.         used[i] = false;
  26.         path.removeLast();
  27.     }
  28. }

总结：
此时可以感受出排列问题的不同：

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了

排列问题是回溯算法解决的经典题目

12.全排列Ⅱ⭐

  • 去重

image.png

  1.     private List<List<Integer>> ans = new ArrayList<>();
  2.     private LinkedList<Integer> path = new LinkedList<>();
  4.     public List<List<Integer>> permuteUnique(int[] nums) {
  5.         boolean[] used = new boolean[nums.length];
  6.         Arrays.sort(nums);
  7.         process(nums, used);
  8.         return ans;
  9.     }
  11.     private void process(int[] nums, boolean[] used) {
  12.         if (path.size() == nums.length) {
  13.             ans.add(new ArrayList<>(path));
  14.             return;
  15.         }
  17.         for (int i = 0; i < nums.length; i++) {
  18.             if ((i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)) {
  19.                 continue;
  20.             }
  22.             if (used[i] == false) {
  23.                 path.add(nums[i]);
  24.                 used[i] = true;
  25.                 process(nums, used);
  26.                 used[i] = false;
  27.                 path.removeLast();
  28.             }
  30.         }
  31.     }

13.重新安排行程⭐⭐
这道题目有几个难点：

  1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
  2. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
  3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
  4. 搜索的过程中，如何遍历一个机场所对应的所有机场。

如何理解死循环？

对于死循环，举一个有重复机场的例子：
image.png
这个例子说明出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环

记录映射关系

  1.  // <出发机场， <目的机场， 航班次数>>
  2.     private Map<String, TreeMap<String, Integer>> map = new HashMap<>();

在遍历 map<出发机场, map<到达机场, 航班次数>> 的过程中，可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。
如果“航班次数”大于零，说明目的地还可以飞，如果如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

回溯法

  1. private boolean process(int ticketNum)

注意函数返回值我用的是bool！
回溯算法一般函数返回值都是void，这次为什么是bool呢？
因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，如图：
image.png
所以找到了这个叶子节点了直接返回

递归终止条件

输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。
所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。

  1.  if (res.size() == ticketNum + 1) {
  2.      return true;
  3.  }

总代码

  1.     private LinkedList<String> res = new LinkedList<>();
  2.     // <出发机场， <目的机场， 航班次数>>
  3.     private Map<String, Map<String, Integer>> map = new HashMap<>();
  5.     public List<String> findItinerary(List<List<String>> tickets) {
  6.         for (List<String> t : tickets) {
  7.             Map<String, Integer> temp;
  8.             if (map.containsKey(t.get(0))) {
  9.                 temp = map.get(t.get(0));
  10.                 temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
  11.             } else {
  12.                 temp = new TreeMap<>(); //升序map
  13.                 temp.put(t.get(1), 1);
  14.             }
  15.             map.put(t.get(0), temp);
  16.         }
  17.         res.add("JFK");
  18.         process(tickets.size());
  19.         return new ArrayList<>(res);
  20.     }
  22.     /**
  23.      * @param ticketNum 航班数量
  24.      */
  25.     private boolean process(int ticketNum) {
  26.         if (res.size() == ticketNum + 1) {
  27.             return true;
  28.         }
  30.         String last = res.getLast();
  31.         if (map.containsKey(last)) {
  32.             for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
  33.                 int count = target.getValue();
  34.                 if (count > 0) {
  35.                     res.add(target.getKey());
  36.                     target.setValue(count - 1);
  37.                     if (process(ticketNum)) return true;
  38.                     target.setValue(count);
  39.                     res.removeLast();
  40.                 }
  41.             }
  42.         }
  43.         return false;
  44.     }

14.N皇后⭐

首先来看一下皇后们的约束条件：

  1. 不能同行
  2. 不能同列
  3. 不能同斜线

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
下面我用一个 3 3 的棋盘，将搜索过程抽象为一棵树，如图：
image.png
从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，*只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

  • 在检查合法性的代码中，可以发现为什么没有在同行进行检查呢？
    • 因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
  1.          List<List<String>> res = new ArrayList<>();
  3.     public List<List<String>> solveNQueens(int n) {
  4.         char[][] chessboard = new char[n][n];
  5.         for (char[] c : chessboard) {
  6.             Arrays.fill(c, '.');
  7.         }
  8.         backTrack(n, 0, chessboard);
  9.         return res;
  10.     }
  12.     private void backTrack(int n, int row, char[][] chessboard) {
  13.         if (row == n) {
  14.             res.add(toList(chessboard));
  15.             return;
  16.         }
  18.         for (int col = 0; col < n; col++) {
  19.             if (isValid(row, col, n,chessboard)) {
  20.                 chessboard[row][col] = 'Q';  //摆放皇后
  21.                 backTrack(n, row + 1, chessboard);
  22.                 chessboard[row][col] = '.';  //回溯
  23.             }
  24.         }
  25.     }
  27.     private boolean isValid(int row, int col, int n, char[][] chessboard) {
  28.         // 检查列
  29.         for (int i = 0; i < row; i++) { //相当于剪枝
  30.             if (chessboard[i][col] == 'Q') {
  31.                 return false;
  32.             }
  33.         }
  35.         // 检查45°对角线
  36.         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
  37.             if (chessboard[i][j] == 'Q') {
  38.                 return false;
  39.             }
  40.         }
  42.         //检查135°对角线
  43.         for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
  44.             if (chessboard[i][j] == 'Q') {
  45.                 return false;
  46.             }
  47.         }
  48.         return true;
  49.     }
  51.     private List<String> toList(char[][] chessboard) {
  52.         List<String> list = new ArrayList<>();
  53.         for (char[] c : chessboard) {
  54.             list.add(String.valueOf(c));
  55.         }
  56.         return list;
  57.     }

棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

15.解数独

N皇后问题(opens new window)是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了，我抽取一部分，如图所示：
image.png

  • 递归函数以及参数

递归函数的返回值需要是bool类型，为什么呢？
因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径

  • 递归单层搜索逻辑

image.png
在树形图中可以看出我们需要的是一个二维的递归（也就是两个for循环嵌套着递归）

  • 一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！

  • 实际上 可以不用两个for循环，而是我们自己来控制， 可以起到剪枝的效果

    1. private boolean process(char[][] board, int i, int j) {
    2.        if (i == 9) {
    3.            return true;
    4.        }
    5.        int nexti = j != 8 ? i : i + 1;
    6.        int nextj = j != 8 ? j + 1 : 0;
    8.        if (board[i][j] != '.') { // 跳过原始数字
    9.            return process(board, nexti, nextj);
    10.        } else {
    11.            for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
    12.                if (isValid(i, j, k, board)) {
    13.                    board[i][j] = k;
    14.                    if (process(board, nexti, nextj)) { //如果找到合适一组立刻返回
    15.                        return true;
    16.                    }
    17.                    board[i][j] = '.';
    18.                }
    19.            }
    20.            // 9个数都试完了，都不行，返回false
    21.            return false;
    22.            // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
    23.            // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
    24.        }
    25. }

    注意这里return false的地方，这里放return false 是有讲究的。
    因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
    那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！

判断棋盘是否合法有如下三个维度：

  • 同行是否重复
  • 同列是否重复
  • 9宫格里是否重复

代码如下：

  1. private boolean isValid(int row, int col, char val, char[][] board) {
  2.         //同行
  3.         for (int i = 0; i < 9; i++) {
  4.             if (board[row][i] == val) {
  5.                 return false;
  6.             }
  7.         }
  9.         //同列
  10.         for (int i = 0; i < 9; i++) {
  11.             if (board[i][col] == val) {
  12.                 return false;
  13.             }
  14.         }
  16.         //九宫格
  17.         int startRow = (row / 3) * 3;
  18.         int startCol = (col / 3) * 3;
  19.         for (int i = startRow; i < startRow + 3; i++) {
  20.             for (int j = startCol; j < startCol + 3; j++) {
  21.                 if (board[i][j] == val) {
  22.                     return false;
  23.                 }
  24.             }
  25.         }
  26.         return true;
  27.     }

  • 总代码

    1. public void solveSudoku(char[][] board) {
    2.       process(board, 0, 0);
    3.   }
    5.   private boolean process(char[][] board, int i, int j) {
    6.       if (i == 9) {
    7.           return true;
    8.       }
    9.       int nexti = j != 8 ? i : i + 1;
    10.       int nextj = j != 8 ? j + 1 : 0;
    12.       if (board[i][j] != '.') { // 跳过原始数字
    13.           return process(board, nexti, nextj);
    14.       } else {
    15.           for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
    16.               if (isValid(i, j, k, board)) {
    17.                   board[i][j] = k;
    18.                   if (process(board, nexti, nextj)) { //如果找到合适一组立刻返回
    19.                       return true;
    20.                   }
    21.                   board[i][j] = '.';
    22.               }
    23.           }
    24.           // 9个数都试完了，都不行，返回false
    25.           return false;
    26.           // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
    27.           // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
    28.       }
    29.   }
    31.   private boolean isValid(int row, int col, char val, char[][] board) {
    32.       //同行
    33.       for (int i = 0; i < 9; i++) {
    34.           if (board[row][i] == val) {
    35.               return false;
    36.           }
    37.       }
    39.       //同列
    40.       for (int i = 0; i < 9; i++) {
    41.           if (board[i][col] == val) {
    42.               return false;
    43.           }
    44.       }
    46.       //九宫格
    47.       int startRow = (row / 3) * 3;
    48.       int startCol = (col / 3) * 3;
    49.       for (int i = startRow; i < startRow + 3; i++) {
    50.           for (int j = startCol; j < startCol + 3; j++) {
    51.               if (board[i][j] == val) {
    52.                   return false;
    53.               }
    54.           }
    55.       }
    56.       return true;
    57.   }

更加优化版本