Generate All Subsets

Problem Generate all subsets (the power set) of a given collection via backtracking.

Input / Output

• Input: array (assume distinct; ask about duplicates). Output: all 2^n subsets.

Constraints

• n <= ~16 (output exponential); with duplicates, output must skip repeated subsets (Subsets II).

Example

• [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]].

Expected approach

• Backtracking: at index i, branch exclude/include nums[i]; emit at i == n — O(2^n · n). Equivalent forms worth knowing: for-loop backtracking (emit every partial, recurse from start index), bitmask enumeration (mask 0..2^n−1), iterative doubling (append each element to all existing subsets). Duplicates variant: sort + skip equal siblings at the same depth. Clean recursion structure and the add/remove (undo) discipline are what get graded.