【专题三:穷举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);}}}
}