P11. 数组的全排列

https://algocasts.io/episodes/ldGj7p9j

Hawstein 好,

我对这道题的类似题有疑问, Leetcode 47 Permutations II, 题意是与Leetcode 46 Permutations I相同, 但是要求是all possible unique permutations.

我想到了以
if(i>0 && nums_list.get(i-1)==nums_list.get(i)) continue;
来去重, 但是会少显示很多 output, 正确做法应该为 Set<Integer> appeared = new HashSet<>(); 然后if(appeared.add(nums_list.get(i)))再进行 swap 和递归.
这里有点糊涂, 希望能得到解答. 多谢!

附全代码

class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();
        if(nums.length==0) return result;
        
        List<Integer> nums_list = new ArrayList<>();
        
        Arrays.sort(nums);
        
        for(int i=0;i<nums.length;i++){
            nums_list.add(nums[i]);
        }
        
        
        permuteUnique_helper(result,nums_list,0);
        
        return result;
        
    }
    
     public void permuteUnique_helper(List<List<Integer>> result, List<Integer> nums_list,int start_index ) {
        if(start_index==nums_list.size()){
            result.add(new ArrayList<>(nums_list));
        }
        
        Set<Integer> appeared = new HashSet<>();
         
        for(int i=start_index;i<nums_list.size();i++){
            // 错误的地方
            // if(i>0 && nums_list.get(i-1)==nums_list.get(i)) continue;
              if(appeared.add(nums_list.get(i))){
            Collections.swap(nums_list,i,start_index);
            permuteUnique_helper(result,nums_list,start_index+1);
            Collections.swap(nums_list,i,start_index);
    }   
        }
            
     }   
}

@110

这里你使用 if(i>0 && nums_list.get(i-1)==nums_list.get(i)) continue; 的问题在于,后面是会进行 swap 的,虽然最开始的地方你对 nums 做了排序。但 swap 后就无序了。对一个无序的数组(或子数组),你不能通过检测 nums[i] 是否等于 nums[i-1] 来做判断。