Given an array of integers that may contain duplicates, ganerate all unique permutations of the array. This problem extends the classic permutation generation by requiring the elimination of duplicate sequences that arise from identical elements.

Key Insight

When elements repeat, naive backtracking produces redundant permutations. For example, with [1, 1, 2], swapping the two 1s yields identical arrangements. To avoid this, we enforce an ordering constraint: only allow the first occurrence of a duplicate value to be placed at a given position unless its predecessor has already been used.

Algorithm Strategy

1. Sort the input — Groups identical elements together, enabling consistent duplicate detection.
2. Use a boolean tracking array — Marks which elements have been included in the current path.
3. Apply pruning during iteration — Skip elements that would lead to duplicates by checking:
   • The current element is already used.
   • The current element equals the previous one, and the previous one hasn't been used yet.

This pruning condition ensures that among identical values, only the leftmost unused one can proceed at each recursion level, effectively enforcing a canonical order.

Implementation

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

    private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] visited, int depth) {
        if (depth == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int index = 0; index < nums.length; index++) {
            if (visited[index]) continue;
            if (index > 0 && nums[index] == nums[index - 1] && !visited[index - 1]) continue;

            visited[index] = true;
            path.add(nums[index]);
            backtrack(result, path, nums, visited, depth + 1);
            path.remove(path.size() - 1);
            visited[index] = false;
        }
    }
}

class Solution:
    def permuteUnique(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        result = []
        path = []
        visited = [False] * len(nums)

        def backtrack(depth):
            if depth == len(nums):
                result.append(path[:])
                return

            for idx in range(len(nums)):
                if visited[idx]:
                    continue
                if idx > 0 and nums[idx] == nums[idx - 1] and not visited[idx - 1]:
                    continue

                visited[idx] = True
                path.append(nums[idx])
                backtrack(depth + 1)
                path.pop()
                visited[idx] = False

        backtrack(0)
        return result

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        vector<int> current;
        vector<bool> taken(nums.size(), false);
        dfs(result, current, nums, taken, 0);
        return result;
    }

private:
    void dfs(vector<vector<int>>& result, vector<int>& current, vector<int>& nums, vector<bool>& taken, int depth) {
        if (depth == nums.size()) {
            result.push_back(current);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (taken[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !taken[i - 1]) continue;

            taken[i] = true;
            current.push_back(nums[i]);
            dfs(result, current, nums, taken, depth + 1);
            current.pop_back();
            taken[i] = false;
        }
    }
};

Why the Condition Works

Consider [1, 1, 2]. At the first level of recursion, both 1s are available. If we allow the second 1 to be chosen before the first, we'd generate duplicate branches. The condition nums[i] == nums[i-1] && !taken[i-1] blocks this by requiring that if two adjacent elements are equal, the left one must be selected first. This enforces a single valid path through identical values, eliminating symmetry-induced duplicates.

Complexity

Time complexity: O(n! / k₁!·k₂!···kₘ!) where kᵢ are frequencies of distinct elements. Space complexity: O(n) for recursion depth and auxiliary arrays.