回溯法（+DFS）：空间换时间（LC46）

回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存状态。

在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节
点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点
状态]。

结合题目加代码注释去理解回溯更加清晰

class Solution {
    public List<List<Integer>> permute(int[] nums) {
         int len=nums.length;
         //使用一个动态数组res保存所有可能的全排列
         List<List<Integer>> res=new ArrayList<>();
          
          if(len==0){
              return res;
          }

          boolean[] used=new boolean[len];
          List<Integer> path=new ArrayList<>();

          dfs(nums,len,0,path,used,res);
          return res;
    }
     //path:往下走一层的时候，path 变量在尾部追加，
      //而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈；

      //depath（index）:表示当前程序递归到第几层,表示当前要确定的是某个全排列中下标为 index 的那个数是多少；
    
    //布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true
    //考虑下一个位置的时候，就能够以 O(1)O(1) 的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。
    private void dfs(int[]nums,int len,int depath,List<Integer>path,boolean[]used,List<List<Integer>> res ){

    if(depath==len){
        res.add(new ArrayList<>(path));//递归结束条件，就是当depath和数组一样，说明找到一组排列
        return;
    }

    // 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
    for(int i=0;i<len;i++){
        if(!used[i]){//未被选择
        path.add(nums[i]);//往栈path里添加未选择的元素
        used[i]=true;//并且将标记为选择过
        

       //找一个等价表达式,就是要向下一层移动depath+1
       dfs(nums,len,depath+1,path,used,res);
        // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
         //上面递归结束，就回溯到上一次
         used[i]=false;
         path.remove(path.size()-1);

    }
}
    }
}