Leetcode 47 - Permutations II

Note:

  • Backtracking question.
  • Need a used[] array
    • Avoid adding a same element multiple times.
    • Avoid duplicates in ans[].
  • It’s easier to write an if statement for continue condition first.
    img

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

1
2
3
4
5
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
nums.sort((a, b) => a - b);
let path = [];
let result = [];
let used = new Set();
backtracking(used);
return result;

function backtracking(used) {
if (path.length === nums.length) {
result.push([...path]);
return;
}

for(let i = 0; i < nums.length; i++) {
if (used.has(i)) continue;
if (nums[i] === nums[i-1] && !used.has(i-1)) continue;
path.push(nums[i]);
used.add(i);
backtracking(used);
path.pop();
used.delete(i);
}
}
};