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

#488 · #78 · Subsets(子集)

📌 Problem Statement & Constraints

Given an integer array nums of unique elements, return all possible subsets (the power set) in any order. Constraints: 1 <= nums.length <= 10, -10 <= nums[i] <= 10.

💡 Core Algorithmic Approaches

  1. Every element is either included or excluded, so there are exactly 2^n subsets.
  2. A DFS over the index decides each element in turn, recording the path at every node (not just at the leaves).
  3. Recording at every node is what produces the partial subsets as well as the full ones.
  4. An iterative bitmask alternative enumerates 0 .. 2^n - 1 and includes element i when bit i is set.

💻 Benchmark Python3 Implementation

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def dfs(i: int, path: List[int]) -> None:
            if i == len(nums):
                res.append(path[:])        # copy, not a reference
                return
            dfs(i + 1, path)               # exclude nums[i]
            path.append(nums[i])
            dfs(i + 1, path)               # include nums[i]
            path.pop()                     # backtrack

        dfs(0, [])
        return res


# Bitmask enumeration: exactly 2^n subsets
class Solution2:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        for mask in range(1 << n):
            res.append([nums[i] for i in range(n) if mask >> i & 1])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * 2^n): there are 2^n subsets, each requiring O(n) to copy.
💾 Space Complexity
O(n) for the recursion path plus O(n * 2^n) for the output.

⚠️ Interview Pitfalls & Follow-ups

  • Appending path without copying: every entry would reference the same list, which is mutated afterwards.
  • Recording only at the leaves: that would produce only the full set, not all subsets.
  • Forgetting path.pop(): the backtracking state would leak between branches.
  • Assuming duplicates may exist: the problem guarantees unique elements, which is why no deduplication is needed (contrast with 90).
⚡
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