DFS
Depth-First-Search，深度优先搜索。

传送门

解决一个回溯问题, 实际上就是一个决策树的遍历过程.
主要思考三个问题:

  1. 路径（已做出的选择）
  2. 选择（当前可做的选择）
  3. 结束条件（决策树的底部，无法再做选择）

代码框架

  1. resule = []
  2. def backtrack(路径，选择列表):
  3.     if(满足结束条件) 
  4.         result.add(路径)
  5.         return;
  7.     for 选择 in 选择列表:
  8.          做选择
  9.         backtrack(路径，选择列表)
  10.         撤销选择

核心就是 for 循环里面的递归, 递归 backtrack() 之前「做选择」, 递归后「撤销选择」.

全排列问题

给出数组 a, [1, 2, 3] , 求出所有的排列组合.
1. 画图
image.png
从根部遍历, 记录路径上的数字, 就是所有的排列.
每个节点都是决策树, 比如下面红点:

image.png
红点中可以做选择 1 或 3, 因为 2 已经是做出的选择, 成为了路径, 而结束条件就是树的底层.
如图:

image.png

image.png

其实也是树的遍历, 只需要处理好选择列表和路径, 所以核心框架为: 

  1. for 选择 in 选择列表:
  2.     # 做选择
  3.     将该选择从选择列表移除
  4.     路径.add(选择)
  5.     backtrack(路径, 选择列表)
  6.     # 撤销选择
  7.     路径.remove(选择)
  8.     将该选择再加入选择列表

Java 代码如下: 

  1.     public static void main(String[] args) {
  2.         //选择列表
  3.         int[] a = new int[]{1, 2, 3};
  4.         //路径
  5.         List<Integer> track = new LinkedList<>();
  6.         //结果
  7.         List<List<Integer>> res = new ArrayList<>();
  8.         backTrack(a, track,res);
  9.         System.out.println(res);
  11.     }
  12.     static void backTrack(int[] nums, List<Integer> track, List<List<Integer>> res) {
  14.         // 5.触发结束条件（路径大小和选择列表大小一致时，为选择列表都选完 ）
  15.         if (track.size() == nums.length) {
  16.             res.add(new ArrayList<>(track));
  17.             return;
  18.         }
  19.         for (int n : nums) {
  20.             // 4.排除不合法选择->track记录下已作出的选择
  21.             if (track.contains(n)) {
  22.                 continue;
  23.             }
  24.             // 1.做选择
  25.             track.add(n);
  26.             // 2.进入下一层决策树
  27.             backTrack(nums, track, res);
  28.             // 3.取消选择
  29.             track.remove(track.size() - 1);
  30.         }
  31.     }

这里并无显式的记录『选择列表』, 而是用 LinkedList.contains() 方法判断元素是否已在『选择列表』。

时间复杂度：DFS - 图5
空间复杂度：DFS - 图6

排列

排列 DFS - 图7 ，且n >= m

公式：DFS - 图8

DFS - 图9

例： A(2,4) = 4*3 = 12

  1. /**
  2.      * 给出数组 int[] a = new int[]{1, 2, 3, 4},
  3.      * 排列组合元素个数 K
  4.      * 列出所有排列可能性
  5.      */
  6.     public static void main(String[] args) {
  7.         //选择列表
  8.         int[] a = new int[]{1, 2, 3, 4};
  9.         int k = 2;
  10.         //路径
  11.         List<Integer> track = new LinkedList<>();
  12.         //结果
  13.         List<List<Integer>> res = new ArrayList<>();
  14.         backTrack(a, k, track, res);
  16.         System.out.println(res.size());
  17.         System.out.println(res);
  18.     }
  19.     static void backTrack(int[] nums, int k, List<Integer> track, List<List<Integer>> res) {
  21.         // 5.触发结束条件
  22.         if (track.size() == k) {
  23.             res.add(new ArrayList<>(track));
  24.             return;
  25.         }
  26.         for (int i = 0; i < nums.length; i++) {
  27.             // 4.排除不合法选择->track记录下已作出的选择
  28.             if (track.contains(nums[i])) {
  29.                 continue;
  30.             }
  31.             // 1.做选择
  32.             track.add(nums[i]);
  33.             // 2.进入下一层决策树
  34.             backTrack(nums, k, track, res);
  35.             // 3.取消选择
  36.             track.remove(track.size() - 1);
  37.         }
  39.    /**
  40.      * n为总数，k为筛选个数，A(m,n)
  41.      */
  42.     static void backTrack1(int n, int k, List<Integer> track, List<List<Integer>> res) {
  43.         // 5.触发结束条件
  44.         if (track.size() == k) {
  45.             res.add(new ArrayList<>(track));
  46.             return;
  47.         }
  48.         for (int i = 0; i < n; i++) {
  49.             // 4.排除不合法选择->track记录下已作出的选择
  50.             if (track.contains(i)) {
  51.                 continue;
  52.             }
  53.             // 1.做选择
  54.             track.add(i);
  55.             // 2.进入下一层决策树
  56.             backTrack1(n, k, track, res);
  57.             // 3.取消选择
  58.             track.remove(track.size() - 1);
  59.         }
  60.     }
  61.     }

组合

组合 DFS - 图10 ，且n >= m

公式：DFS - 图11
DFS - 图12

例: C(2, 4) = (43) / (21) = 6

  1.   /**
  2.      * 给出数组 int[] a = new int[]{1, 2, 3, 4};
  3.      * 列出所有组合可能性 
  4.      * 
  5.      * 
  6.      *  此问题等同于 排列组合C（m,n）问题  C(2,4) = 6
  7.      *  与排列不同的是，组合的数据无序，排列的数据有序 如（1，4）和（4，1）对于排列是两组数据，对于组合只是一组
  8.      */
  9.     public static void main(String[] args) {
  10.         //选择列表
  11.         int[] a = new int[]{1, 2, 3, 4};
  12.         //路径
  13.         List<Integer> track = new LinkedList<>();
  14.         int k = 2;
  15.         //结果
  16.         List<List<Integer>> res = new ArrayList<>();
  17.         backTrack(a, k, 0, track, res);
  18.         System.out.println(res.size());
  19.         System.out.println(res);
  20.     }
  22.    /**
  23.      * 与上基本相同
  24.      * n为总个数，k为筛选个数 C(k,n)
  25.      */
  26.     static void backTrack(int[] nums, int k, int start, List<Integer> track, List<List<Integer>> res) {
  27.         // 5.触发结束条件
  28.         if (track.size() == k) {
  29.             res.add(new ArrayList<>(track));
  30.              return;
  31.         }
  32.         for (int i = start; i < nums.length; i++) {
  33.             // 4.排除不合法选择->track记录下已作出的选择
  34.             if (track.contains(nums[i])) {
  35.                 continue;
  36.             }
  37.             // 1.做选择
  38.             track.add(nums[i]);
  39.             // 2.进入下一层决策树
  40.             backTrack(nums, k, i, track, res);
  41.             // 3.取消选择
  42.             track.remove(track.size() - 1);
  43.         }
  45.            static void backTrack1(int n, int k, int start, List<Integer> track, List<List<Integer>> res) {
  47.         // 5.触发结束条件
  48.         if (track.size() == k) {
  49.             res.add(new ArrayList<>(track));
  50.             return;
  51.         }
  52.         for (int i = start; i < n; i++) {
  53.             // 4.排除不合法选择->track记录下已作出的选择
  54.             if (track.contains(i)) {
  55.                 continue;
  56.             }
  57.             // 1.做选择
  58.             track.add(i);
  59.             // 2.进入下一层决策树
  60.             backTrack1(n, k, i, track, res);
  61.             // 3.取消选择(回溯状态)
  62.             track.remove(track.size() - 1);
  63.         }
  64.     }
  65.    }