💬 Discord
Sign In
NeetCode #494LC-47MediumBacktrackingNC 250
← Back to All Problems

#494 · #47 · Permutations II(全排列 II)

📌 Problem Statement & Constraints

Given a collection of numbers nums that may contain duplicates, return all unique permutations in any order. Constraints: 1 <= nums.length <= 8, -10 <= nums[i] <= 10.

💡 Core Algorithmic Approaches

  1. Sort the array so duplicates are adjacent, then use the used array template.
  2. The deduplication rule: skip nums[i] when it equals nums[i-1] and nums[i-1] has not been used -- meaning the previous duplicate has already been consumed in this position.
  3. This ensures each distinct permutation is generated exactly once.
  4. The not used[i-1] condition is the subtle part and is worth stating precisely.

💻 Benchmark Python3 Implementation

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()                        # duplicates become adjacent
        res = []
        used = [False] * len(nums)

        def dfs(path: List[int]) -> None:
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                # skip a duplicate whose earlier copy is already used in this path
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs(path)
                path.pop()
                used[i] = False

        dfs([])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * n!): bounded by the number of distinct permutations.
💾 Space Complexity
O(n) for the path and the used array.

⚠️ Interview Pitfalls & Follow-ups

  • Using if nums[i] == nums[i-1]: continue without the used condition: legitimate permutations would be dropped.
  • Using used[i-1] instead of not used[i-1]: the rule is inverted and duplicates slip through.
  • Not sorting: the adjacency of duplicates is what makes the rule work.
  • Using a set of tuples for deduplication: O(n) extra per permutation; the in-place rule is free.