Subsets

Problem

Package managers compute dependency sets by enumerating all possible subsets of available packages to find valid install combinations. Given an integer array with distinct elements, return all possible subsets (the power set). The result must contain every combination from the empty set to the full array, with no duplicates.

Input: [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
 
Input: [0]
Output: [[], [0]]

Solution

Approach: Backtracking with a start index, recording the path at every node.

The recursion walks a decision tree where each node is a partial subset. The key move is result.append(path[:]) at the very top of backtrack, before the loop runs - every node in the tree, not just the leaves, is a valid subset. The root call records the empty set, then the loop from start to the end tries each remaining element: append it, recurse with index + 1, then pop it back off. Passing index + 1 (never index) means each deeper level only considers elements that come after the current one, so the algorithm builds each subset in a fixed left-to-right order and never produces the same combination twice. Trace [1, 2, 3]: the root records [], picks 1 and recurses to record [1], then [1, 2], then [1, 2, 3]; it pops back up and picks 3 from the [1] level to get [1, 3], and so on - 8 nodes, 8 subsets. The path[:] copy is essential: path is a single shared list mutated in place, so storing the reference would leave every saved subset pointing at the same eventually-empty list.

Edge cases: An empty input still records [] on the first call before the empty loop runs, giving [[]]. A single element yields exactly the empty set and itself.

Complexity: O(n * 2^n) time, O(n) space - 2^n subsets, each costing O(n) to copy; recursion depth and path are both bounded by n (output excluded).