深度遍历算法，简称“暴力搜索”，不撞南墙不回头
理念：三位数，每一位都遍历三遍和布尔值搭配判断，并且递归到下一位，回溯，位数上限判断
image.png

行为分析

123 因为触底条件回收，3被置为false
12 因为遍历结束回收，2被置为false
回到1 ，1接着遍历3 （3虽然被用过但是已经被false了，所以在这里可以再用）

应用分析

递归三大元素（和循环三大元素一样）
初始化在main方法调用时
判断在方法头，
如果初始值是1，输入值是3，那判断就要在4截断 ；如果初始值是0，输入值是3，那判断就要在3截断
总之判断是用来判断越界的，不是用来判断最后一层的。
递归的改变
并用boolean值
boolean其实就是用来判断for循环的i是否被用过，置true
回溯重置
在递归方法后紧跟，置false（代表回溯的时候，这层数置false）

本题分析

因为我们要从第一位开始算，然后通过循环把所以初始值为0
boolean其实就是用来判断for循环的i是否被用过

  1. public class dfs {
  2.     static boolean[] booleans = new boolean[10];
  3.     static int bound;
  4.     static int[] nums = new int[10];
  5.     static void dfsVoid(int u) {
  6.         if (u==bound){
  7.             for (int i = 0; i<bound;i++){
  8.                 System.out.print(nums[i]+" ");
  9.             }
  10.             System.out.println();
  11.             return;
  12.         }
  13.         for (int i = 1; i <= bound; i++) {
  14.             if (!booleans[i]){
  15.                 nums[u] = i;
  16.                 booleans[i] = true;
  17.                 dfsVoid(u+1);
  18.                 booleans[i] = false;
  19.             }
  20.         }
  21.     }
  23.     public static void main(String[] args) {
  24.         Scanner sc = new Scanner(System.in);
  25.         bound = sc.nextInt();
  26.         dfsVoid(0);
  27.     }
  28. }

image.png

核心思想

递归和循环的区别

递归的本质就是循环，把递归放在一个循环中，就相当于两个循环嵌套。
递归值的初始化就是入参的第一个数 ; 递归的限定条件就是在方法开头的那个条件语句中限定return了，和循环的限定条件一个道理；递归的递增是在传参中体现。这样一看和循环的语法（初始化，限定条件，自增/自减）是一样的，只不过它分布在了递归作用域的其他各个角落。

递归线程回收

递归的线程是从后往前挨个回收的。就像我们这的案例数据u = 123一样，1,2,3分别在for循环中入参递归了。比如第一轮，
是0入参递归以后，在for循环i=1的时候就开始递归了。
然后1入参递归以后，在i=2的时候入参了。
然后2入参递归以后，在i=3的时候return（因为1，2已用）。
打印第一个数字123

开始回收
回收的时候3已经是循环i=3了，所以直接到18行，结束线程。
回收第2层的时候循环i=2，所以接着递归i=3
数组结果这时候变成 ，13_

理解回溯重置

booleans[i] = false;
为什么这个语句要放在递归后面，因为但凡是有线程来到这个语句，它必定return了，必定return代表它已经打印过。打印过了我们再解开这个数给倒数第二个线程使用，也就是倒数第二层可以调用到这个数。因为第二层没用过第三层用过的数，所以逻辑上通。。
它必定return了。是不是有dfs的感觉了，只有当return了，最外层这个数才会被解开，然后给上一层用。
相当于u控制层数，i控制数字，boolean控制i是否用过，当进入下一层boolean为true用过，当return数字后boolean为false没用过。供给上一层使用。上一层因为下一层return，也直接false给再上一层使用。

总结

每一层都遍历123看哪个没用过，直到return以后，再从最后一个线程（在本题就是第三层）挨个回收，回收就是挨个线程继续执行。比如第三层执行完循环了，第三层这个线程回收，并且按照接下来的代码运行，也就是3这个数解开为false。到观察第二层，第二层遍历到2，所以还要接着遍历3的递归情况。所以递归和dfs这种执行理念是一致的，每一层都是这么不断深入，直到穷尽return。