Code Implementation

class Solution:
    def permuteUnique(self, nums):
        res = []
        nums.sort()
        used = [False] * len(nums)
        
        def backtrack(path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack(path)
                path.pop()
                used[i] = False
        
        backtrack([])
        return res
      

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, used, path, res);
        return res;
    }
    
    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used, path, res);
            path.pop_back();
            used[i] = false;
        }
    }
};
      

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), res);
        return res;
    }
    
    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}
      

var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b);
    const res = [];
    const used = Array(nums.length).fill(false);
    function backtrack(path) {
        if (path.length === nums.length) {
            res.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.push(nums[i]);
            backtrack(path);
            path.pop();
            used[i] = false;
        }
    }
    backtrack([]);
    return res;
};
      

Problem Description

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

• Each number in nums may only be used once in each permutation.
• Permutations must not contain duplicates: if two permutations are identical, only one should be returned.
• The input nums can contain duplicate numbers.

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

Thought Process

The problem asks for all possible permutations of a list of numbers, but with a twist: the list can contain duplicates, and we must avoid returning duplicate permutations.

The brute-force approach would generate every possible permutation (even duplicates) and then filter out duplicates at the end, perhaps by using a set or hash map. However, this is inefficient, especially for lists with many repeated elements.

To optimize, we want to avoid generating duplicates in the first place. This requires a way to "skip" over repeated permutations as we build them, rather than removing them afterward. We can do this by:

• Sorting the input array so that duplicates are adjacent.
• Ensuring that for any duplicate number, we only use it if the previous duplicate has already been used in the current permutation path.

Solution Approach

We use a backtracking algorithm to generate permutations, but with special care to avoid duplicates.

1. Sort the input array: This puts duplicates next to each other, making them easier to identify.
2. Use a "used" array: Track which elements have already been included in the current permutation.
3. Backtracking function: At each step, try to add an unused number to the current path.
4. Skip duplicates smartly: When considering an element at index i, if it is the same as the previous element (nums[i] == nums[i-1]), only use it if nums[i-1] has already been used in the current path. This ensures we don't swap identical elements and create duplicate permutations.
5. Base case: When the current path has the same length as nums, add a copy of it to the result.
6. Backtrack: After exploring one path, undo the last choice (remove the last number and mark it as unused).

This approach guarantees that each unique permutation is generated exactly once and avoids unnecessary computation.

Example Walkthrough

Let's walk through the input nums = [1,1,2].

1. Sort nums: [1,1,2]
2. Start with an empty path [] and all elements unused.
3. First position:
   • Pick 1 (index 0): path is [1], mark index 0 as used.
   • Next position:
     • Pick 1 (index 1): path is [1,1], mark index 1 as used.
     • Next position:
       • Pick 2 (index 2): path is [1,1,2] (length = 3), add to results.
     • Backtrack: remove last, unmark index 2.
   • Backtrack: remove last, unmark index 1.
   • Pick 2 (index 2): path is [1,2], mark index 2 as used.
   • Next position:
     • Pick 1 (index 1): path is [1,2,1], add to results.
   • Backtrack: remove last, unmark index 2.
4. Backtrack: remove last, unmark index 0.
5. Pick 1 (index 1): Normally, we would skip this if index 0 is unused (to avoid duplicate permutations starting with the second 1). Since index 0 is unused, we skip.
6. Pick 2 (index 2): path is [2], mark index 2 as used.
   • Pick 1 (index 0): path is [2,1], mark index 0 as used.
   • Pick 1 (index 1): path is [2,1,1], add to results.

The unique permutations are [[1,1,2], [1,2,1], [2,1,1]].

Time and Space Complexity

• Brute-force approach: Generates all n! permutations and removes duplicates at the end. Time complexity is O(n! * n) (for generating and storing permutations), plus extra time for deduplication.
• Optimized approach (backtracking with skipping duplicates): Still potentially O(n! * n) in the worst case (as all unique permutations must be generated and stored), but avoids generating duplicate permutations, making it much faster in practice for inputs with many duplicates.
• Space complexity: O(n!) for storing the result, plus O(n) for the recursion stack and helper arrays.

The key improvement is that the optimized approach only generates unique permutations, saving both time and space compared to the brute-force method.

Summary

To solve the Permutations II problem, we use backtracking with careful duplicate-skipping logic. By sorting the input and only using a duplicate number if its previous duplicate has already been used, we avoid generating repeated permutations. This approach is both efficient and elegant, ensuring that only unique permutations are produced and avoiding unnecessary computation.