subsets.py

from typing import List


class Solution:
    """LeetCode #78 - Subsets (Medium)
    https://leetcode.com/problems/subsets/

    Return the power set of `nums` (all distinct values). There are 2^n subsets,
    so no algorithm can beat O(2^n) - the output alone is that big.
    """

    def subsets(self, nums: List[int]) -> List[List[int]]:
        """Backtracking: for each element, branch on take it / skip it.

        Key insight: a subset is just a sequence of independent yes/no decisions,
        one per element. The recursion makes both choices at every index, so the
        tree of calls has 2^n leaves - and each leaf is one subset.

        The three-line backtracking rhythm is worth memorising, because every
        problem in this block reuses it:

            choose  -> subset.append(...)
            explore -> backtrack(i + 1)
            undo    -> subset.pop()

        That "undo" is what makes it *backtracking* rather than plain recursion:
        one shared list is mutated and restored instead of copying it at every
        step.

        `subset[:]` is not optional - appending `subset` itself would store a
        reference to the live list, and every recorded answer would end up empty
        once the recursion unwinds. A classic and very confusing bug.

        Time:  O(n * 2^n) - 2^n subsets, each copied in O(n).
        Space: O(n)       - recursion depth and the working list (output aside).
        """
        result = []
        subset = []

        def backtrack(i: int) -> None:
            if i == len(nums):            # every element has been decided
                result.append(subset[:])  # snapshot, not a reference
                return

            subset.append(nums[i])        # branch 1: take nums[i]
            backtrack(i + 1)
            subset.pop()                  # undo before trying the other branch

            backtrack(i + 1)              # branch 2: skip nums[i]

        backtrack(0)
        return result