Medium Include / Exclude Recursion
In plain English: Generate every possible subset of a list of elements (the power set).
Each element has exactly two choices: include or exclude — this binary decision tree has 2^n leaves, one per subset.
Prompt
Generate all subsets (power set) of a list of numbers.
Try to write it from scratch before scrolling down.
Solution
# Recursive
def subsets(nums):
if not nums:
return [[]]
rest = subsets(nums[1:])
return rest + [[nums[0]] + s for s in rest] # include/exclude first element
# Iterative
def subsets_iter(nums):
result = [[]]
for x in nums:
result += [s + [x] for s in result]
return result
# Test: subsets([1,2,3]) => 8 subsets