Backtracking: all subsets

The power set of a list is the collection of all its subsets — including the empty set and the full set. A list of k distinct elements has 2 ** k subsets.

Backtracking explores choices one element at a time: for each element you either include it or skip it, recursing on the rest. When you run out of elements, the choices you've made so far form one subset.

def build(i, current):
    if i == len(nums):
        record(current)          # one complete subset
        return
    build(i + 1, current)        # skip nums[i]
    build(i + 1, current + [nums[i]])  # include nums[i]

Your task

Write subsets(nums) where nums is a list of distinct integers. Return a list of all subsets. To keep the output deterministic so it can be checked:

1. each subset must be a list in ascending order, and
2. the returned list of subsets must be sorted(...) (Python's default list ordering).

subsets([1, 2])     # [[], [1], [1, 2], [2]]
subsets([])         # [[]]
subsets([1, 2, 3])  # [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Hint: generate every subset, do sorted(subset) on each, collect them into a list, and finish with return sorted(all_subsets).