47.Permutations_II

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]]

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

analyze

[1 1 2]

• 1
  • 1
    • 2
  • 2
    • 1
• 1 (jump, 该位置上 1 已经在之前被使用过了, 因此需跳过)
• 2
  • 1
    • 1
  • 1 (jump)

思路: 回溯法解排列问题。

需要注意此题允许 nums 里面存有相同的数字。在此引入 used 数组来存储回溯过程中已使用的值。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const res = []
  backtracking(nums, [], [], res)
  return res
};

var backtracking = function(nums, used, temp, res) {
  if (temp.length === nums.length) {
    for (let i = 0; i < res.length; i++) {
      // a digit appears only once.
      if (res[i].toString() === temp.toString()) return
    }
    res.push([...temp])
    return
  }

  for (let i = 0; i < nums.length; i++) {
    // jump same used index.
    if (used.indexOf(i) > -1) continue
    temp.push(nums[i])
    used.push(i)
    backtracking(nums, used, temp, res)
    temp.pop(nums[i])
    used.pop(i)
  }
}

上述解法在去重的步骤上比较耗时, 提交的时候报超时错误, 进行如下优化:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const res = []
  const sortNums = nums.sort((r1, r2) => r1 - r2)
  backtracking(sortNums, [], [], res)
  return res
};

var backtracking = function(nums, used, temp, res) {
  if (temp.length === nums.length) {
    res.push([...temp])
    return
  }

  for (let i = 0; i < nums.length; i++) {
    // 如果当前下标被使用过或者当前下标对应的值已经在之前被使用过了, 则跳过。
    if (used.indexOf(i) > -1 || (nums[i] === nums[i - 1] && used.indexOf(i - 1) === -1)) continue
    temp.push(nums[i])
    used.push(i)
    backtracking(nums, used, temp, res)
    temp.pop(nums[i])
    used.pop(i)
  }
}