【专题三:穷举vs暴搜vs深搜vs回溯vs剪枝】46. 全排列

1.题目解析

2.讲解算法原理  

1.首先画出决策树，越详细越好

2.设计代码

• 全局变量
  • List<List<Integer>> ret
  • List<Integer> path
  • boolean[] check 
• dfs函数
  • 仅关心某一节点在干什么
• 细节问题
• 回溯
  • 干掉path最后一个元素
  • 修改check权限
• 剪枝
  • check中为true的不能使用，要剪掉
• 递归出口
  • 遇到叶子结点的时候，直接添加结果

3.编写代码 

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;

    public List<List<Integer>> permute(int[] nums) {
        ret=new ArrayList<>();
        path=new ArrayList<>();
        check=new boolean[nums.length];
        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums){
        if(nums.length==path.size()){
            ret.add (new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(check[i]==false){
                path.add(nums[i]);
                check[i]=true;
                dfs(nums);
                //回溯，恢复现场
                check[i]=false;
                path.remove(path.size()-1);
            }
            
            
        }
    }
}