Subsets

Problem

Given an array of distinct integers nums, produce every possible subset of its elements, including the empty set and the full set. The order of subsets in the output, and the order of elements within a subset, does not matter, but no subset may appear twice.

• Up to 12 elements.
• Each value is between -15 and 15.
• All elements are distinct.

Examples

• nums = [5, 6, 9] → [[], [5], [6], [9], [5,6], [5,9], [6,9], [5,6,9]] in any order. 2^3 = 8 subsets.
• nums = [3] → [[], [3]].
• nums = [2, 8] → [[], [2], [8], [2,8]].

Hints

1. For each element you make an independent yes/no decision. How many total outcomes does that give, and how would you enumerate them?
2. Build subsets incrementally: after deciding about the first i elements, recurse on the rest. Every partial path is itself a valid subset.
3. Backtracking with a start index (only add elements after the last one chosen) guarantees each subset is generated exactly once. A bit-mask loop from 0 to 2^n - 1 is the iterative alternative.