Subsets

Given an array of distinct integers, return all possible subsets (the power set).

Example

Input: 1 2 3 Output: 8 subsets, including the empty one and 1 2 3 itself

Approach

At each recursive call, the current partial subset is itself a valid answer — record it, then try extending it with each remaining element in turn, recursing, then removing the element again ("un-choosing") before trying the next one.

Walkthrough

1def bt(start, path):
2    result.append(list(path))
3    for i in range(start, len(nums)):
4        path.append(nums[i])
5        bt(i + 1, path)
6        path.pop()

Input format

Line 1: the array, space-separated

Print the total subset count on the first line, then each subset (space-separated values) on its own line, in the order your backtracking produces them.