Permutations II

Problem Description

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

Examples

Constraints

• 1 ≤ nums.length ≤ 8
• -10 ≤ nums[i] ≤ 10

The Trick Is When to Skip

Permutations I assumed all elements were unique. Here, duplicates mean you can’t just check if an element is used. Two copies of 1 look identical, so if you place either one first, you get the same permutation. You need to break that symmetry.

Sort the array. Use a used boolean array. The skip rule: if nums[i] == nums[i-1] and !used[i-1], skip nums[i]. The !used[i-1] condition means “we’re at the same recursion level as when we tried the previous identical value.” If used[i-1] is true, the previous copy is already in our current permutation at a deeper position, and this is a genuinely different arrangement.

This condition is subtle. Getting it wrong generates either duplicates or misses valid permutations.

Solution: Backtracking with Used Array

import java.util.*;

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

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

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // skip if same value as previous AND previous wasn't used at a deeper level
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            current.add(nums[i]);
            backtrack(nums, used, current, result);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

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

        def backtrack(current: list[int]):
            if len(current) == len(nums):
                result.append(current[:])
                return

            for i in range(len(nums)):
                if used[i]:
                    continue
                # skip if same value as previous AND previous wasn't used at a deeper level
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue

                used[i] = True
                current.append(nums[i])
                backtrack(current)
                current.pop()
                used[i] = False

        backtrack([])
        return result

#include <vector>
#include <algorithm>

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

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

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

            used[i] = true;
            current.push_back(nums[i]);
            backtrack(nums, used, current, result);
            current.pop_back();
            used[i] = false;
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n * n!) in the worst case (all unique). With duplicates, the pruning reduces actual work, but the upper bound stays the same.
• Space Complexity: O(n) for the recursion stack and used array.

Where it breaks: the condition !used[i-1] is the hard part. If you use used[i-1] (without the negation), you’d allow duplicates through. If you drop the condition entirely, you’d skip valid permutations. Test with [1,1,2] and verify you get exactly 3 permutations, not 6.

Common Mistakes

• Negating used[i-1] incorrectly. The skip fires when the previous identical element is NOT currently in use, i.e., when we’re choosing at the same level. If the previous was used, it’s at a deeper position in the permutation and this is a different arrangement.
• Forgetting to sort. Without sorting, equal values aren’t adjacent and the duplicate check doesn’t work.
• Using i > 0 with both used[i-1] conditions but forgetting the outer if (used[i]). You need both checks: skip if already in the permutation, and skip if it’s a duplicate at the same level.

Frequently Asked Questions

Why does the condition use !used[i-1] and not used[i-1]? When used[i-1] is false, it means the previous copy of the same value was already tried and backtracked at this recursion level. Trying the current copy would produce the exact same set of permutations. When used[i-1] is true, the previous copy is sitting at a different position in the current arrangement, so this is a genuinely distinct permutation.

Is there a way to do this without sorting? Yes, using a frequency map to track remaining counts. But it’s more complex and slower in practice for small inputs like this.

← All Problems