Subsets

Problem: Return all subsets of distinct integers.

function backtrack(nums, index, current, result):
    result.add(copy of current)
    for i from index to nums.length - 1:
        current.add(nums[i])
        backtrack(nums, i + 1, current, result)
        current.removeLast()

Example: $[1,2,3]$ → $[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]$.

Time: $O(n \cdot 2^n)$. Space: $O(n)$.