Consider the set $S = \left\{1, 2, 3, 4, 5, 6, 7, 9\right\}$. Prove that you can make a list of all of 256 subsets of $S$ so that each subset occurs exactly once, the empty set is first in the list, and each subset in the list after the first is obtained by either adding one element to the preceding subset or deleting one element from the preceding subset.
I tried to solve this question using graph theory, but so far I haven't gotten any result. Can you find any pattern from the solution? I have tried smaller problems like 4 and 5 elements, but still didn't get any sense.
The simple proof is by induction on the number of elements of $S$. For a one element set $\{1\}$ you can do $\emptyset, \{1\}$. Now suppose you can do it with $k$ elements in $S$. We can create such a list for $k+1$ elements by making the list for the first $k$ elements in $S$, then adding the $k+1^{st}$ element to the last subset, then reversing the original list with $k+1$ added to each one. Continuing our example, we have the answer for $k=1$, then our list for $k=2$ is $\emptyset, \{1\}, \{1,2\}, \{2\}$