LeetCode Problem

Problem Description

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

Examples

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

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

Follow-up

Approach to Solve

Use backtracking with sorting to generate all possible unique permutations.

Code Implementation

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path, counter):
            if len(path) == len(nums):
                result.append(path[:])
                return
            for num in counter:
                if counter[num] > 0:
                    path.append(num)
                    counter[num] -= 1
                    backtrack(path, counter)
                    path.pop()
                    counter[num] += 1
        
        result = []
        backtrack([], Counter(nums))
        return result

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, boolean[] used) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            used[i] = true;
            tempList.add(nums[i]);
            backtrack(result, tempList, nums, used);
            used[i] = false;
            tempList.remove(tempList.size() - 1);
        }
    }

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        vector<int> path;
        backtrack(nums, used, path, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used, path, result);
            used[i] = false;
            path.pop_back();
        }
    }

Explanation

This solution uses a backtracking approach to generate all possible permutations of the input array nums, ensuring no duplicates. Here's a detailed explanation of the algorithm:

Initialize an empty list result to store the resulting permutations.
Sort the input array nums to handle duplicates.
Call the backtrack function with the initial parameters: result, an empty list path, the sorted input array nums, and a boolean array used to track which elements have been used in the current permutation.
In the backtrack function:
- If the size of path is equal to the length of nums, add a copy of path to result and return.
- Iterate through each number in nums:
  - If the number is already in path, skip it.
  - Add the number to path.
  - Recursively call backtrack with the updated parameters.
  - Remove the last added number from path (backtrack).
Return the result list containing all unique permutations of nums.

The time complexity is O(n!) for generating all permutations, and the space complexity is O(n) for the recursion stack and to store each permutation.

Complexity

Time Complexity: O(n * n!)
Space Complexity: O(n)

LeetSolved

Permutations II