Permutations II

Difficulty: Medium Source: NeetCode

Problem

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Permutations I — the version with all distinct elements
• Backtracking — building permutations position by position with a used array
• Duplicate handling — sort-and-skip applied to permutations

1. Brute Force

Intuition

Generate all permutations using the standard used-array approach (from Permutations I), convert each one to a tuple, and add it to a set to deduplicate. Simple, but we still do redundant work exploring branches that produce duplicate permutations.

Algorithm

1. Sort nums (optional for brute force but good habit).
2. Backtrack with a used array; at base case, convert to tuple and add to a set.
3. Return the set converted to list of lists.

Solution

def permuteUnique_brute(nums):
    result_set = set()
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result_set.add(tuple(current))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False

    backtrack([])
    return [list(t) for t in result_set]


print(sorted(permuteUnique_brute([1, 1, 2])))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Complexity

• Time: O(n! * n) — explores all permutations, hashing each
• Space: O(n! * n) — storing all permutations in a set

2. Backtracking with Sorted Duplicate Skip

Intuition

Sort nums so duplicates are adjacent. Use the used array approach from Permutations I. Before placing nums[i] at the current position, add a skip condition: if i > 0 and nums[i] == nums[i-1] and used[i-1] is False, skip nums[i]. This rule says: “don’t place nums[i] at this position if an identical earlier element is available but hasn’t been placed yet.” This enforces a consistent ordering where duplicate values are always picked left-to-right, eliminating duplicate permutations without needing a set.

Algorithm

1. Sort nums.
2. Initialize used = [False] * len(nums).
3. Define backtrack(current).
4. If len(current) == len(nums): append a copy and return.
5. For each i:
   • Skip if used[i].
   • Skip if i > 0 and nums[i] == nums[i-1] and not used[i-1].
   • Mark used, append, recurse, pop, unmark.

Solution

def permuteUnique(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(list(current))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            # skip: same value as previous, and previous hasn't been used yet
            # this ensures we always use the left duplicate before the right one
            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


print(permuteUnique([1, 1, 2]))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
print(permuteUnique([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
print(permuteUnique([1, 1, 1]))
# [[1, 1, 1]]

Complexity

• Time: O(n! * n) — in the worst case (all distinct), n! permutations; duplicates reduce this
• Space: O(n) — recursion depth plus used array

Common Pitfalls

The skip condition feels backwards. not used[i-1] checks that the previous duplicate has NOT been used. This ensures that when you try to place nums[i] (a duplicate of nums[i-1]), nums[i-1] was placed before nums[i] in a previous call — enforcing left-to-right order for duplicates. If you use used[i-1] (the opposite), you’d generate far more duplicates.

Forgetting to sort. Without sorting, nums[i] == nums[i-1] won’t reliably detect duplicates since they may not be adjacent.

Using a set to deduplicate instead of pruning. A set works but is wasteful — you pay the cost of generating and hashing duplicate permutations. The not used[i-1] pruning avoids generating duplicates in the first place.