47 Permutations II

Leetcode

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

---

和 46 题类似。不过难度明显增加。

在 1，1，2 这种情况下，有 6 种排列，去掉重复的只有 1-1-2 ， 1-2-1 ， 2-1-1 这 3 种排列。第 1 个数字，如果选了 1 ，就不能再选另一个 1 。如果把数字按顺序排列，当一个数字和上一个数字相同时，如果上一个数字没有被选过，说明重复了。

     1      1‘      2
    / \    /  \    /  \
   1'  2   1   2   1   1'     
 /    /   /   /   /   /
 2   1'  2   1   1'  1   

如图，第一行前 2 个，如果选了 1 ，那么 1‘ 就不能再选。第二行后 2 个，如果选了 1 ，那么 1’ 就不能再选。把数组排序，就可以用上一个数字是否选过来判断是否是重复的。

class Solution {
    List<List<Integer>> ret;
    List<Integer> list;
    boolean[] visited;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret=new LinkedList<>();
        list=new ArrayList<>();
        visited=new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, 0);
        return ret;
        
    }
    
    private void dfs(int[] nums, int index){
        if(index==nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=0;i<nums.length;++i){
            if(visited[i]) continue;
            if(i>0 && nums[i]==nums[i-1] && !visited[i-1]) continue;
            list.add(nums[i]);
            visited[i]=true;
            dfs(nums, index+1);
            list.remove(index);
            visited[i]=false;
        }
    }                             
}