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

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
  • used数组记录当前的数有没有被用过；为什么要记录？因为might contain duplicates所以如果数字相同并不知道应该怎么区分当前这个大小的数字之前有没有被用过，所以要用used;
  • 既然是相当于“伴随状态数组的”used, 所以回溯的时候也要回溯这个;
  • 跟花花的permutation模版吻合

很重要: subset II也是不能有duplicates, 但是只是判断i > 0 && nums[i] == nums[i-1],因为subset, set，只要数字相同就不行; 而这里permutations II中，如果本身nums中的数就有相同的，那么这两个相同的数是可以都有的，所以唯一区别这种数的方法就是used数组记录有没有被用过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(list, new ArrayList<>(), nums, new boolean[nums.length]);
        return list;
    }
    
    public void dfs(List<List<Integer>> list, List<Integer> arr, int[] nums, boolean[] used) {
        if (arr.size() == nums.length) list.add(new ArrayList<>(arr));
        for (int i = 0; i < nums.length; ++i) {
            if (used[i] || i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = true;
            arr.add(nums[i]);
            dfs(list, arr, nums, used);
            
            used[i] = false;
            arr.remove(arr.size() - 1);
        }
    }
}