LeetCode-全排列（回溯+递归）

（一）题目描述

给定一个不含重复数字的数组 

nums

 ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

（二）思路

那道题首先想到的就是遍历（深度优先或广度优先），此题利用深度优先遍历，然后利用回溯，直至所有排列情况均被罗列，具体可参考以下网址解题：力扣（解决此类题目最好画出生成树）

tips：通过此题，结合了idea的debug进行步骤跟踪，对递归的执行过程终于有了一点点眉目，本人有以下理解：递归无非就是一层一层的往里面调用，每调用一次函数，该新函数就会开辟属于自己的一片函数空间，此时旧函数就会保持在原来执行的进度，当下一个函数返回时，该函数又会接着原来停止的点开始执行。

（三）代码如下：

class Solution16 {
    List<List<Integer>>res;
    public List<List<Integer>> permute(int[] nums) {
        res=new ArrayList<>();
        boolean[] used=new boolean[nums.length]; //记录哪些数已经被用过
        dfs(nums,new ArrayList<>(),used,0);
        return res;
    }
    private void dfs(int[] nums,List<Integer>path,boolean[] used,int depth){
        if(depth== nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        //每进行一次函数调用，i都是从0开始循环，所以需要使用used数组记录该数是否被使用过
        for (int i = 0; i <nums.length ; i++) {
            if(used[i]==true){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            dfs(nums,path,used,depth+1);
            //执行到这一步时，表明上一步的递归已经进行了返回，所以需要进行状态重置；
            //若不清楚递归调用流程，建议使用debug
            //path.size()-1不影响i的变化，而且没调用一个递归函数就相当于开辟了一个新的函数空间，当该空间调用函数跳到下一空间去执行另一函数时，该空间的各种状态依然会保存，到结果返回时，该函数会从停止的地方继续执行
            path.remove(path.size()-1);
            used[i]=false;
        }
    }
}