Return all subsets (the power set) of the given distinct integers.
subsets(nums)
Produce them by starting from {{}} and, for each new element, adding it to copies of
every subset so far. This yields the order shown below.
Input format: space-separated integers. Output: each subset's values joined by
spaces, subsets separated by ; (the empty subset is an empty segment).
[1, 2] // → {}, {1}, {2}, {1,2} serialized: ";1;2;1 2"
[1, 2, 3] // → 8 subsets
[] // → {} serialized: ""
The power set is every possible subset, including empty and full. With n distinct elements there are 2ⁿ subsets, since each element independently is either in a given subset or not. That "in or out" framing unlocks the whole problem.
Before looking at any elements, there's one subset: empty. For the first element, every subset so far splits into an excluding copy (unchanged) and an including copy (plus this element) — the count doubles. Repeat for each subsequent element: every existing subset again splits into excluding and including copies. After n elements, you've doubled n times — 2ⁿ subsets, covering every in/out combination exactly once.
A classic recursive backtrack: for each element, recurse once including it and once excluding it, recording the subset when elements run out — directly mirroring the include/exclude tree.
A tidy iterative version avoids recursion: keep a running list of subsets, starting with just the empty one. For each new element, go through every subset currently in the list and push a copy plus the new element. Snapshotting the list's length before the loop means you don't reprocess newly created subsets in the same pass. Same doubling behavior as the recursive tree, just breadth-first across elements instead of depth-first.
Generating subsets by size (0, 1, 2, ... n) and combining separately is more bookkeeping for no benefit — it's just combinations for every k, concatenated. The doubling technique does essentially the minimum work: each of the 2ⁿ subsets costs O(n) to construct, no more.
Since each new element only extends existing subsets (never modifies earlier ones), and copies are appended after originals, subsets come out grouped in the specific order shown: empty set first, then singles, then pairs including the newest element, and so on.
def subsets(nums):
result = [[]]
for n in nums:
size = len(result)
for i in range(size):
result.append(result[i] + [n])
return result
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.