Categories
Uncategorized

47. Permutations II Leetcode Javascript Solution

The Problem:

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

The Solution:

For this kind of problem, we’ll need to use backtracking. We also implement a boolean array with the same length as that of the number array to keep track of visited elements (because the number array contains duplicates):

var permuteUnique = function(nums) {
let results = []
nums.sort((a,b) => a-b)
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))
return results
};

Leave a Reply

Your email address will not be published. Required fields are marked *