78. Subsets
You get an array nums of distinct integers (not necessarily sorted). Produce its power set — every subset, from the empty set all the way up to the full array. An array of n elements has exactly 2^n subsets.
Return the subsets as a list of lists in one canonical form so grading is deterministic: inside each subset the values appear in increasing order, and the subsets themselves are ordered first by size (smallest first) and, among equal sizes, lexicographically by their values. For nums = [1, 2, 3] that ordering is [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].
Example 1:
Input: nums = [1, 2, 3]
Output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
Explanation: All 2³ = 8 subsets: the empty set, the three singletons, the three pairs, then the whole array.
Example 2:
Input: nums = [0]
Output: [[], [0]]
Explanation: A single element has two subsets: keep it or leave it out.
Constraints:
- 1 ≤ nums.length ≤ 10
- -10 ≤ nums[i] ≤ 10
- All values in nums are distinct
Hints:
A subset is nothing more than n independent keep/skip decisions — one per element. That is exactly why there are 2^n of them, and why an n-bit integer can encode one subset per value from 0 to 2^n − 1.
Sort nums first — the canonical order compares numeric values, and sorting makes both the within-subset order and the tie-breaking fall out naturally.
To emit the required order directly, generate combinations of each size 0, 1, …, n over the sorted array using start-index backtracking — the same skeleton as the Combinations problem, run once per size.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3]
Expected output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]