全排列-DFS

复仇Bytedance之路

题目描述：

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

题解

其实像这种类型的题目有很多，因此dfs是一种必须要掌握的方法 DFS视频讲解

深度优先搜索

class Solution { public List<List<Integer>> permute(int[] nums) { //他的本质还是一个数组 List<List<Integer>> res =new ArrayList<>(); //首先是特判 int len = nums.length; if(len==0){ return res; } //记录元素的使用情况，空间换时间 boolean[] used =new boolean[len]; //记录当前路径 List<Integer> path =new ArrayList<>(); dfs(nums,len,0,path,used,res); return res; } //depth 是记录当前深度 public void dfs(int[] nums,int len,int depth,List<Integer> path,boolean[] used,List<List<Integer>>res){ //回溯首先就需要写回溯的终止条件 if(depth==len){ //到了最后一层了，把当前path记录下来吧。 res.add(new ArrayList<> (path)); } for(int i=0 ;i<len;i++){ //首先要确保这个元素没有被用过 if(!used[i]){ path.add(nums[i]); used[i]=true;//标记状态 //深度加一 dfs(nums,len,depth+1,path,used,res); //最后一层已经搜索完了，会回到倒数第二层 dfs这条语句执行完 //状态重置,与上面是相反的 used[i]=false; path.remove(path.size() - 1); } } } }

上面这种情况是没有重复元素的，那如果存在重复元素的时候怎么办？剪枝操作！

剪枝操作的前提是：元素需要排序!!!

class Solution { public List<List<Integer>> permute(int[] nums) { //他的本质还是一个数组 List<List<Integer>> res =new ArrayList<>(); //首先是特判 int len = nums.length; if(len==0){ return res; } // 排序（升序或者降序都可以），排序是剪枝的前提 Arrays.sort(nums); //记录元素的使用情况，空间换时间 boolean[] used =new boolean[len]; //记录当前路径 List<Integer> path =new ArrayList<>(); dfs(nums,len,0,path,used,res); return res; } //depth 是记录当前深度 public void dfs(int[] nums,int len,int depth,List<Integer> path,boolean[] used,List<List<Integer>>res){ //回溯首先就需要写回溯的终止条件 if(depth==len){ //到了最后一层了，把当前path记录下来吧。 res.add(new ArrayList<> (path)); } for(int i=0 ;i<len;i++){ //首先要确保这个元素没有被用过 if(!used[i]){ if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; } path.add(nums[i]); used[i]=true;//标记状态 //深度加一 dfs(nums,len,depth+1,path,used,res); //最后一层已经搜索完了，会回到倒数第二层 dfs这条语句执行完 //状态重置,与上面是相反的 used[i]=false; path.remove(path.size() - 1); } } } }

来看看这句话

//剪枝 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; } nums[i] == nums[i - 1 两次的元素相同!used[i - 1] 这里为什么有这个！，原因是当我搜索到重复元素i时，我前一个相同的元素i-1的状态刚刚被重置为true