47. Permutations II Решение Leetcode Javascript

Проблема:

Учитывая набор чисел nums, который может содержать дубликаты, вернуть все возможные уникальные перестановки в любом порядке.

Пример 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Пример 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]]

Ограничения:

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

Решение:

Для такого рода задач нам нужно использовать поиск с возвратом. Мы также реализуем логический массив той же длины, что и массив чисел, чтобы отслеживать посещенные элементы (поскольку массив чисел содержит дубликаты):

var permuteUnique = function(nums) {
let results = []
nums.sort((a,b) => ab)
function backtrack(nums,results, temp,used){
if(temp.length == nums.length){
results.push([…temp])
}
for(let i = 0; i ‹ nums.length ; i++){
// console.log(used + " "+ i + " " + temp)
if(used[i] || (i › 0 && nums[i] == nums [i-1] && used[i — 1]) ){continue}
used[i] = true
temp.push(nums[i])
backtrack(nums,results, temp, used)
used[i] = false
temp.pop()
}
}
backtrack(nums,results, new Array(), new Array (nums.length).fill(false))
вернуть результаты
};