聊聊leetcode可包含重复数字的序列的《47. 全排列 II》中的vis标记函数

序列的《47. 全排列 II》中的vis标记函数"/>

聊聊leetcode可包含重复数字的序列的《47. 全排列 II》中的vis标记函数

1 题目描述（字节二面题目）

2 代码

class Solution {List<List<Integer>>res;List<Integer>list;boolean[]used;public List<List<Integer>> permuteUnique(int[] nums) {res=new ArrayList<>();list=new ArrayList<>();used=new boolean[nums.length];Arrays.sort(nums);dfs(nums,0);return res;}void dfs(int[]nums,int s){if(list.size()==nums.length){res.add(new ArrayList<>(list));return;}for(int i=0;i<nums.length;i++){if(used[i]||(i>0&&nums[i]==nums[i-1]&&!used[i-1])){ // #Acontinue;}list.add(nums[i]);used[i]=true;dfs(nums,i);list.remove(list.size()-1);used[i]=false;}}
}

3 关于2中的#A处代码的解析

这是一行关于剪枝的判断语句，具体有两个重要的判断条件(used[i]||(i>0&&nums[i]==nums[i-1]&&!used[i-1]))，满足其中任一个都可以跳过当前元素的遍历，我们都知道第一条件是用于判断向下遍历时，当前准备选取的元素是否已经在路径中，如果used[i]==true，则跳过；第二个条件是用于去重判断，我们在dfs函数运行之前对数组进行了排序，在横向遍历的时候需要进行去重（i>0&&nums[i]==nums[i-1]），但是我们得确定怎么样算是横向遍历，关键就是!used[i-1]这个代码，我们都知道dfs函数会对used[i-1]进行回溯，当我们横向遍历到第i个元素时，则used[0…(i-1)]都必然是false才能满足横向遍历的判断。

3.1 那这个!used[i-1]可以去掉吗？

当然不能，因为只有带上这个，i>0&&nums[i]==nums[i-1]才会仅仅在横向判断的时候起作用，如果不带这个，那么这个去重代码还会在纵向遍历的时候起作用。

以nums=[1,1,2]为例，如果dfs函数的#A行带上，那么输出[[1,1,2],[1,2,1],[2,1,1]]，如果去掉#A行的!used[i-1]，则返回[]。

为什么后者会导致输出为空列表呢？
答：去掉!used[i-1]，导致去重操作也发生在了纵向遍历的过程中，当遍历到第二个1时，used[0]为true或者false都不重要，都会因为i>0&&nums[i]==nums[i-1]的判断导致被剪枝。