Introduction to Subsets Pattern

You are given a set of distinct numbers. Produce every possible subset.

[1, 5, 3]

[], [1], [5], [1, 5], [3], [1, 3], [5, 3], [1, 5, 3]

For every number, there are two choices:

1. Include it.
2. Do not include it.

With three numbers, there are 2 * 2 * 2 = 8 subsets. With N numbers, there are 2^N subsets.

We need a method that builds all of them without missing or repeating any result.

Start with the empty subset. For each input number, copy every existing subset and add the number to each copy.

start:   []
add 1:   [], [1]
add 5:   [], [1], [5], [1, 5]