题目

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

Example:

  1. Input: [1,1,2]
  2. Output:
  3. [
  4.   [1,1,2],
  5.   [1,2,1],
  6.   [2,1,1]
  7. ]

题意

求给定数组的全排列，注意数组中有重复元素。

思路

与 0046. Permutations (M) 相比，多了重复元素，只要在46解法基础上加上相应的限制即可。

  1. 回溯法：
    • 使用hash：用一张hash表记录整个搜索中对应下标的数是否已被使用，每一层递归中再用一张hash表记录当前递归层次中已经插入过(又移除)的数字，每次操作都往已有序列后插入一个未被使用的数(既是整个搜索中未被使用，也是当前递归中未被使用)，更新hash，递归，再移除改数，更新hash。
    • 不使用hash：对于结果序列中的每一个位置index，它可能存放的数为nums从index到最后一个位置nums.length-1中的任意一个数，但要保证每次存放的都是不同的数。所以每次操作都从这(nums.length - index)个数中选出一个，并判断该数是否已经存放过，若没有则放到当前空位，再对右边的空位进行递归操作。
  2. 结合 0031. Next Permutation (M) 来实现全排列。

代码实现

Java

回溯法无hash

  1. class Solution {
  2.     public List<List<Integer>> permuteUnique(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         permute(nums, 0, ans);
  5.         return ans;
  6.     }
  8.     private void permute(int[] nums, int index, List<List<Integer>> ans) {
  9.         if (index == nums.length - 1) {
  10.             List<Integer> list = new ArrayList<>();
  11.             for (int i = 0; i < nums.length; i++) {
  12.                 list.add(nums[i]);
  13.             }
  14.             ans.add(list);
  15.             return;
  16.         }
  18.         for (int i = index; i < nums.length; i++) {
  19.             // 每次都要判断该数是否已经使用过
  20.             boolean flag = false;
  21.             for (int j = index; j < i; j++) {
  22.                 if (nums[i] == nums[j]) {
  23.                     flag = true;
  24.                     break;
  25.                 }
  26.             }
  27.             if (flag) {
  28.                 continue;
  29.             }
  31.             swap(nums, index, i);
  32.             permute(nums, index + 1, ans);
  33.             swap(nums, index, i);
  34.         }
  35.     }
  37.     private void swap(int[] nums, int i, int j) {
  38.         int temp = nums[i];
  39.         nums[i] = nums[j];
  40.         nums[j] = temp;
  41.     }
  42. }

回溯法hash

  1. class Solution {
  2.     public List<List<Integer>> permuteUnique(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         permute(nums, new boolean[nums.length], new ArrayList<>(), ans);
  5.         return ans;
  6.     }
  8.     private void permute(int[] nums, boolean[] hash, List<Integer> list, List<List<Integer>> ans) {
  9.         if (list.size() == nums.length) {
  10.             ans.add(new ArrayList<>(list));
  11.         }
  13.         // 当前递归中也要用一张hash表记录已经插入过的数字
  14.         Set<Integer> used = new HashSet<>();
  15.         for (int i = 0; i < nums.length; i++) {
  16.             if (!hash[i] && !used.contains(nums[i])) {
  17.                 used.add(nums[i]);
  18.                 list.add(nums[i]);
  19.                 hash[i] = true;
  20.                 permute(nums, hash, list, ans);
  21.                 hash[i] = false;
  22.                 list.remove(list.size() - 1);
  23.             }
  24.         }
  25.     }
  26. }

nextPermutation

  1. class Solution {
  2.     public List<List<Integer>> permuteUnique(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         Arrays.sort(nums);
  5.         while (true) {
  6.             List<Integer> list = new ArrayList<>();
  7.             for (int i = 0; i < nums.length; i++) {
  8.                 list.add(nums[i]);
  9.             }
  10.             ans.add(list);
  11.             if (hasNextPermutation(nums)) {
  12.                 nextPermutation(nums);
  13.             } else {
  14.                 break;
  15.             }
  16.         }
  17.         return ans;
  18.     }
  20.     // 根据当前排列计算下一个排列 
  21.     private void nextPermutation(int[] nums) {
  22.         int i = nums.length - 2;
  23.         while (i >= 0 && nums[i] >= nums[i + 1]) {
  24.             i--;
  25.         }
  26.         int j = nums.length - 1;
  27.         while (nums[j] <= nums[i]) {
  28.             j--;
  29.         }
  30.         swap(nums, i, j);
  31.         reverse(nums, i + 1, nums.length - 1);
  32.     }
  34.     // 判断是否存在下一个排列，即判断是否已经是完全逆序数列
  35.     private boolean hasNextPermutation(int[] nums) {
  36.         int i = nums.length - 2;
  37.         while (i >= 0 && nums[i] >= nums[i + 1]) {
  38.             i--;
  39.         }
  40.         return i >= 0;
  41.     }
  43.     private void reverse(int[] nums, int left, int right) {
  44.         while (left < right) {
  45.             swap(nums, left++, right--);
  46.         }
  47.     }
  49.     private void swap(int[] nums, int i, int j) {
  50.         int temp = nums[i];
  51.         nums[i] = nums[j];
  52.         nums[j] = temp;
  53.     }
  54. }

JavaScript

回溯法无hash

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  let lists = []
  dfs(nums, 0, lists)
  return lists
}


let dfs = function (nums, index, lists) {
  if (index === nums.length) {
    lists.push([...nums])
    return
  }

  let used = new Set()
  for (let i = index; i < nums.length; i++) {
    if (!used.has(nums[i])) {
      used.add(nums[i]);
      [nums[index], nums[i]] = [nums[i], nums[index]]
      dfs(nums, index + 1, lists);
      [nums[index], nums[i]] = [nums[i], nums[index]]
    }
  }
}

回溯法hash

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  let lists = []
  dfs(nums, 0, [], lists, new Set())
  return lists
}

let dfs = function (nums, index, list, lists, record) {
  if (index === nums.length) {
    lists.push([...list])
    return
  }

  let used = new Set()
  for (let i = 0; i < nums.length; i++) {
    if (!record.has(i) && !used.has(nums[i])) {
      used.add(nums[i])
      record.add(i)
      list.push(nums[i])
      dfs(nums, index + 1, list, lists, record)
      list.pop()
      record.delete(i)
    }
  }
}