Subsets – Solution & Complexity

Watch: Subsets with take-or-skip backtracking

Each number is either in a subset or not, so n numbers give 2ⁿ subsets. Backtracking walks that decision tree: at index i, take the number, recurse, pop it, then skip it and recurse. When i reaches the end, save a copy of the path. The iterative version starts from the empty set and doubles the list for each number. O(n · 2ⁿ) time, O(n) extra space besides the output.

Solution Walkthrough

  1. Step 1: Understand the Goal

    • Identify the required output and the state that changes.
    • Use the examples to rule out tempting but incorrect interpretations.
  2. Step 2: Choose the Core Pattern

    • This problem is best exposed by Backtracking makes an include/exclude decision for each value.
    • Maintain only the state needed for the next operation.
  3. Step 3: Build the Algorithm

    • Process each state once when possible.
    • Record state before scheduling dependent work to avoid duplicates.
  4. Step 4: Check Edge Cases

    • Verify the smallest input, impossible cases, and repeated values where allowed.
    • Keep output ordering deterministic.
  5. Step 5: Final Solution and Complexity

    • Time complexity is O(n*2^n).
    • Space complexity is O(n*2^n).
    def subsets(nums: list[int]) -> list[list[int]]:
        answer, current = [], []
        def backtrack(index):
            if index == len(nums):
                answer.append(current.copy()); return
            current.append(nums[index]); backtrack(index + 1); current.pop()
            backtrack(index + 1)
        backtrack(0)
        return answer

FAQ