leetcode46.全排列——学习笔记

题目：力扣https://leetcode-cn.com/problems/permutations/

class Solution {
    public List> permute(int[] nums) {
        List> ans = new ArrayList>();
        int len = nums.length;
        int depth = 0;
        Deque path = new ArrayDeque<>();
        boolean[] used = new boolean[len];
        dfs(nums,len,depth,path,used,ans);
        return ans;
    }

    private void dfs(int[] nums,int len,int depth,Deque path,boolean[] used,List> ans){
        if(depth == len){
            ans.add(new ArrayList<>(path));
            return;
        }

        for(int i=0;i 
 
 
 思路：深度优先遍历。写一个深度优先的递归方法，每往下一层就减少一个可以选择的数，直到最层数与数组长度相同时即表示已经填写好了一个解，将这个解添加到ans中。我觉得这题的难点不在递归，而是在于回溯的时候，需要重置状态，这个“重置”该怎么做在一开始困扰了我一阵，后来学习完题解之后，发现通过Deque类的path和boolean类的used[]数组可以轻松解决。
 
1.声明需要用到的变量。len变量表示nums[]数组的长度；depth变量表示当前处在哪一层；Deque类型的path是一个双端队列，支持高速的插入，之后需要用这个容器记录深度优先遍历的路径；boolean类型的uesd[]数组，用于记录当前位置nums[]数组中哪些元素不可用。
 
List> ans = new ArrayList>();
int len = nums.length;
int depth = 0;
Deque path = new ArrayDeque<>();
boolean[] used = new boolean[len];
 
2.写一个深度优先的递归方法，将需要用到的参数传进去。
 
    private void dfs(int[] nums,int len,int depth,Deque path,boolean[] used,List> ans){
    //......
}
 
3.设置递归出口。当层数depth等于nums[]数组长度len时，表示已经填完了一个解，将path放入一个新List中再添加到ans中。
 
if(depth == len){
    ans.add(new ArrayList<>(path));
    return;
}
 
4.循环遍历nums[]数组，先根据used[]数组的值判断当前元素是否可用，若不可用则continue到下一次循环，若可用则将当前元素加入到path中，接着修改当前元素的uesd[]值为不可用。随后继续递归调用dfs()进入到下一层的元素填充过程。再回溯时，需要将之前填写的数据删除，将used[]的值更改回“可用”，这就是重置状态。
 
for(int i=0;i 
4.在主方法中调用dfs()方法，执行完这个方法之后，ans已经记录着各个解，我们只需要将ans返回即可。
 
dfs(nums,len,depth,path,used,ans);
return ans;