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

Solutions:

Python

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # Initialize an empty list to store the permutations
        permutations = []

        # Sort the array so that we can skip duplicates when generating permutations
        nums.sort()

        # Use a backtracking search to generate the permutations
        self.backtrack(permutations, [], nums, [False] * len(nums))

        return permutations

    def backtrack(self, permutations: List[List[int]], currentPermutation: List[int], nums: List[int], used: List[bool]):
        # If the current permutation is the same length as the original array, we have found a permutation
        if len(currentPermutation) == len(nums):
            permutations.append(currentPermutation[:])
            return

        # Otherwise, try adding each unused number to the current permutation and recursively search for more permutations
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                # Skip this number if it is already used or if it is a duplicate of the previous number and the previous number is not used
                continue

            # Mark the number as used and add it to the current permutation
            used[i] = True
            currentPermutation.append(nums[i])

            # Recursively search for more permutations
            self.backtrack(permutations, currentPermutation, nums, used)

            # Backtrack by marking the number as unused and removing it from the current permutation
            used[i] = False
            currentPermutation.pop()

C#

public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        // Initialize an empty list to store the permutations
        IList<IList<int>> permutations = new List<IList<int>>();

        // Sort the array so that we can skip duplicates when generating permutations
        Array.Sort(nums);

        // Use a backtracking search to generate the permutations
        Backtrack(permutations, new List<int>(), nums, new bool[nums.Length]);

        return permutations;
    }

    private void Backtrack(IList<IList<int>> permutations, IList<int> currentPermutation, int[] nums, bool[] used) {
        // If the current permutation is the same length as the original array, we have found a permutation
        if (currentPermutation.Count == nums.Length) {
            permutations.Add(new List<int>(currentPermutation));
            return;
        }

        // Otherwise, try adding each unused number to the current permutation and recursively search for more permutations
        for (int i = 0; i < nums.Length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                // Skip this number if it is already used or if it is a duplicate of the previous number and the previous number is not used
                continue;
            }

            // Mark the number as used and add it to the current permutation
            used[i] = true;
            currentPermutation.Add(nums[i]);

            // Recursively search for more permutations
            Backtrack(permutations, currentPermutation, nums, used);

            // Backtrack by marking the number as unused and removing it from the current permutation
            used[i] = false;
            currentPermutation.RemoveAt(currentPermutation.Count - 1);
        }
    }
}

Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Initialize an empty list to store the permutations
        List<List<Integer>> permutations = new ArrayList<>();

        // Sort the array so that we can skip duplicates when generating permutations
        Arrays.sort(nums);

        // Use a backtracking search to generate the permutations
        backtrack(permutations, new ArrayList<>(), nums, new boolean[nums.length]);

        return permutations;
    }

    private void backtrack(List<List<Integer>> permutations, List<Integer> currentPermutation, int[] nums, boolean[] used) {
        // If the current permutation is the same length as the original array, we have found a permutation
        if (currentPermutation.size() == nums.length) {
            permutations.add(new ArrayList<>(currentPermutation));
            return;
        }

        // Otherwise, try adding each unused number to the current permutation and recursively search for more permutations
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                // Skip this number if it is already used or if it is a duplicate of the previous number and the previous number is not used
                continue;
            }

            // Mark the number as used and add it to the current permutation
            used[i] = true;
            currentPermutation.add(nums[i]);

            // Recursively search for more permutations
            backtrack(permutations, currentPermutation, nums, used);

            // Backtrack by marking the number as unused and removing it from the current permutation
            used[i] = false;
            currentPermutation.remove(currentPermutation.size() - 1);
        }
    }
}

Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    // Initialize an empty list to store the permutations
    const permutations = [];

    // Sort the array so that we can skip duplicates when generating permutations
    nums.sort();

    // Use a backtracking search to generate the permutations
    backtrack(permutations, [], nums, nums.map(() => false));

    return permutations;
};

var backtrack = function(permutations, currentPermutation, nums, used) {
    // If the current permutation is the same length as the original array, we have found a permutation
    if (currentPermutation.length === nums.length) {
        permutations.push([...currentPermutation]);
        return;
    }

    // Otherwise, try adding each unused number to the current permutation and recursively search for more permutations
    for (let i = 0; i < nums.length; i++) {
        if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
            // Skip this number if it is already used or if it is a duplicate of the previous number and the previous number is not used
            continue;
        }

        // Mark the number as used and add it to the current permutation
        used[i] = true;
        currentPermutation.push(nums[i]);

        // Recursively search for more permutations
        backtrack(permutations, currentPermutation, nums, used);

        // Backtrack by marking the number as unused and removing it from the current permutation
        used[i] = false;
        currentPermutation.pop();
    }
}

Typescript

function permuteUnique(nums: number[]): number[][] {
     // Initialize an empty list to store the permutations
    const permutations: number[][] = [];

    // Sort the array so that we can skip duplicates when generating permutations
    nums.sort();

    // Use a backtracking search to generate the permutations
    backtrack(permutations, [], nums, new Array(nums.length).fill(false));

    return permutations;
};

function backtrack(permutations: number[][], currentPermutation: number[], nums: number[], used: boolean[]): void {
    // If the current permutation is the same length as the original array, we have found a permutation
    if (currentPermutation.length === nums.length) {
        permutations.push([...currentPermutation]);
        return;
    }

    // Otherwise, try adding each unused number to the current permutation and recursively search for more permutations
    for (let i = 0; i < nums.length; i++) {
        if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
            // Skip this number if it is already used or if it is a duplicate of the previous number and the previous number is not used
            continue;
        }

        // Mark the number as used and add it to the current permutation
        used[i] = true;
        currentPermutation.push(nums[i]);

        // Recursively search for more permutations
        backtrack(permutations, currentPermutation, nums, used);

        // Backtrack by marking the number as unused and removing it from the current permutation
        used[i] = false;
        currentPermutation.pop();
    }
}

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique(array $nums): array {
        // Initialize an empty list to store the permutations
        $permutations = [];

        // Sort the array so that we can skip duplicates when generating permutations
        sort($nums);

        // Use a backtracking search to generate the permutations
        $this->backtrack($permutations, [], $nums, array_fill(0, count($nums), false));

        return $permutations;
    }

    function backtrack(array &$permutations, array $currentPermutation, array $nums, array $used): void {
        // If the current permutation is the same length as the original array, we have found a permutation
        if (count($currentPermutation) === count($nums)) {
            $permutations[] = $currentPermutation;
            return;
        }

        // Otherwise, try adding each unused number to the current permutation and recursively search for more permutations
        for ($i = 0; $i < count($nums); $i++) {
            if ($used[$i] || ($i > 0 && $nums[$i] === $nums[$i - 1] && !$used[$i - 1])) {
                // Skip this number if it is already used or if it is a duplicate of the previous number and the previous number is not used
                continue;
            }

            // Mark the number as used and add it to the current permutation
            $used[$i] = true;
            $currentPermutation[] = $nums[$i];

            // Recursively search for more permutations
            $this->backtrack($permutations, $currentPermutation, $nums, $used);

            // Backtrack by marking the number as unused and removing it from the current permutation
            $used[$i] = false;
            array_pop($currentPermutation);
        }
    }
}

I hope this helps! Let me know if you have any questions. Don’t forget to follow and give some like to support my content

https://medium.com/@araneznorman