### 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 <= numsi <= 10

### analyze

1 1 2

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

``````/**
* @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)
}
}``````