Subsets

Learning goal: Recognize why an array of n distinct elements has exactly 2^n subsets.

Core idea For every element, there are two independent decisions: include it in the current subset or leave it out. A complete sequence of these binary decisions identifies exactly one subset. The algorithm must also include the empty subset, which corresponds to excluding every element.

Algorithm plan

• Start with an empty partial subset.
• Make a decision for each element, either include or exclude.
• Record every partial subset when the recursion reaches that decision point.
• Return the collection of recorded subsets.

Micro-example For [0], excluding 0 gives []; including 0 gives [0]. Thus the answer contains two subsets.

Pitfalls

• Forgetting to record [] loses a valid answer.
• Treating the output order as significant can lead to unnecessary constraints.
• The input values are distinct, so duplicate-handling logic is not needed.

Recap

• Each element contributes two choices.
• The empty subset is always part of the answer.
• The total number of results is 2^n.

Learning goal: Understand how the include/exclude idea becomes a backtracking search.

Core idea A decision tree can represent the problem directly. At the node for an element, one branch skips it and the other branch adds it. The backtracking implementation uses a shared path to represent the current subset, then removes the most recently added value when returning from recursion.

Algorithm plan

• At index i, consider nums[i].
• Explore the exclude branch without changing path.
• Explore the include branch after appending nums[i].
• Undo the append before returning to the caller.

Micro-example From path = [1], the next element 2 creates [1] when excluded and [1, 2] when included. Later, the same pattern applies to 3.

Pitfalls

• Recording only at leaves misses shorter subsets such as [1].
• Forgetting the undo step causes one branch's values to leak into another.
• The recursion must preserve the input order while exploring choices.

Recap

• Include and exclude are complementary branches.
• Every recursion state is a valid subset.
• Backtracking means choose, recurse, and undo.

Learning goal: Translate the search tree into a concise recursive procedure.

Core idea Use a function backtrack(start) where path stores the current subset. First copy path into the results; then loop from start through the remaining indices. For each candidate, append it, recurse from the next index, and pop it to restore the previous state.

Algorithm plan

def backtrack(start):
    results.append(path.copy())
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1)
        path.pop()

Micro-example At start = 1 with path = [1], the loop tries 2, then undoes it, then tries 3. This produces [1, 2] and [1, 3] without duplicates.

Pitfalls

• Pass i + 1, not start or i, to advance the search.
• Append a copy of path, not the mutable list itself.
• Always pop after the recursive call.

Recap

• Record first, then choose each remaining element.
• Recurse on the next index.
• Undo exactly one choice after each recursive call.

Learning goal: Trace one complete depth-first execution and connect each state to an output subset.

Core idea The traversal records a subset when it enters a recursive call. It then tries each remaining element in order. The depth of the call reflects how many elements are currently in path; after a recursive branch finishes, pop() returns the path to its parent state.

Algorithm plan

• Begin at start = 0 with path = []; record [].
• Choose 1, then explore 2, then 3.
• Backtrack from [1, 2, 3] to [1, 2], then to [1].
• From [1], choose 3 to record [1, 3].
• Return to the root and repeat the same process beginning with 2, then 3.

Micro-example The depth-first order is [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]. These are all eight subsets, with no repetition.

Pitfalls

• A visualization should show the undo step, not just the forward choices.
• The current path must be copied when recorded.
• A branch with no remaining choices still contributes its current subset.

Recap

• Every visited state becomes an output.
• Increasing indices prevent reuse and duplication.
• Undoing choices lets one shared path represent many branches.

Learning goal: Prevent duplicate outputs and incorrect shared-state behavior.

Core idea Backtracking is correct only when each recursive call owns a well-defined prefix of choices. The start index ensures that a branch moves forward through the input, while pop() ensures that the mutable path is restored before the next branch begins.

Common failure modes

Micro-example After exploring [1, 2], the path must return to [1] before trying 3. If 2 remains in the shared list, the algorithm may incorrectly produce [1, 2, 3] again or distort a stored result.

Pitfalls

• Do not sort or deduplicate the result for this problem; distinct input values already guarantee uniqueness.
• Be careful at start == n: record the current path, then return.
• Copy mutable paths at the moment they are recorded.

Recap

• Advance with i + 1.
• Undo every append.
• Record a snapshot, not the shared list.

Learning goal: Justify the O(n · 2^n) time bound and O(n) recursion space.

Core idea There are 2^n subsets, so the algorithm must produce exponentially many results. Copying a current subset can cost up to O(n), making the total output-related work O(n · 2^n). The recursion path contains at most n selected elements, so the auxiliary call stack and path use O(n) space, excluding the returned output.

Algorithm plan

• Record the current path.
• Loop through candidates from start onward.
• Choose one candidate and recurse with the next index.
• Undo the choice and continue.
• Stop when all branches have been explored.

Micro-example For n = 3, the algorithm records 8 subsets. The longest copied subset has length 3, and the deepest recursion also has depth 3.

Pitfalls

• Do not describe the space as only O(1); the recursion and current path grow with n.
• If counting the output, storing all subsets requires O(n · 2^n) space.
• The exponential time is unavoidable when the required output itself is exponential.

Recap

• Time: O(n · 2^n) including path copies.
• Auxiliary recursion space: O(n).
• Include, recurse, undo, and record every state.