⚡Flashcard Drill➔
NeetCode #493LC-90MediumBacktrackingNC 150NC 250
← Back to All Problems

#493 · #90 · Subsets II(子集 II)

📌 Problem Statement & Constraints

Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets. Constraints: 1 <= nums.length <= 10, -10 <= nums[i] <= 10.

💡 Core Algorithmic Approaches

  1. Sort the array so duplicates are adjacent, then use the loop-based subset template.
  2. Record the path at every node, since every partial selection is a valid subset.
  3. Deduplicate at each recursion level by skipping a value equal to its predecessor in the same loop.
  4. The level-local skip is what removes duplicate subsets while keeping legitimate repeated values in deeper levels.

💻 Benchmark Python3 Implementation

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()                        # duplicates become adjacent
        res = []

        def dfs(start: int, path: List[int]) -> None:
            res.append(path[:])            # every node is a valid subset
            for j in range(start, len(nums)):
                # skip duplicates at THIS level only
                if j > start and nums[j] == nums[j - 1]:
                    continue
                path.append(nums[j])
                dfs(j + 1, path)
                path.pop()

        dfs(0, [])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * 2^n): there are at most 2^n subsets, each copied in O(n).
💾 Space Complexity
O(n) for the recursion path plus the output.

⚠️ Interview Pitfalls & Follow-ups

  • Using j > 0 in the duplicate skip: values legitimately repeated at deeper levels would be wrongly skipped, losing valid subsets.
  • Not sorting: duplicates would not be adjacent and the skip would not work.
  • Recording only at the leaves: that would produce only the full set.
  • Using a set of tuples for deduplication: O(n) extra work per subset; the level-local skip is free.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems