This is an algorithm that is sufficiently important that, while we will encourage you to come up with your own solution, we will also give you our solution.

The other issue you will find is that the algorithm presented actually solves more than one problem.

Suppose we have a set of five unique objects, let's call them ${a, b, c, d}$. I would like to step through all possible subsets; for example,

${}$,
${a}, {b}, {c}, {d}$
${a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}$
${a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}$
${a, b, c, d}$

Now, looking at how I listed these, you can probably see how I created these subsets; however, it would be very difficult for me to describe how to, for example, create all subsets.

If you care, you can read this description, but it is not very useful.

Without reading further, try to come up with your own algorithm that would go through all possible subsets.

A solution

This is the easiest-to-program of most algorithms. Consider each entry as being either present or missing, and at each step, you can toggle (change) it from being present to missing or vice versa.

• 1. Start with all entries as missing.
• 2. Starting with the last entry:
• 2a. Toggle its presence.
• 2b. If all entries are present, we are finished.
• 2c. If its presence is being toggled from missing to present, we are done, go back to Step 2;
• 2d. otherwise, move to the previous entry and return to Step 2a.

If we start with ${a, b, c, d}$ and let $\times$ represent a missing entry, we now have:

${\times, \times, \times, \times} = {}$ ${\times, \times, \times, d} = {d}$ ${\times, \times, c, \times} = {c}$ ${\times, \times, c, d} = {c, d}$ ${\times, b, \times, \times} = {b}$ ${\times, b, \times, d} = {b, d}$ ${\times, b, c, \times} = {b, c}$ ${\times, b, c, d} = {b, c, d}$ ${a, \times, \times, \times} = {a}$ ${a, \times, \times, d} = {a, d}$ ${a, \times, c, \times} = {a, c}$ ${a, \times, c, d} = {a, c, d}$ ${a, b, \times, \times} = {a, b}$ ${a, b, \times, d} = {a, b, d}$ ${a, b, c, \times} = {a, b, c}$ ${a, b, c, d} = {a, b, c, d}$

Choice of sign

Suppose we want to consider $\pm k$ for all values in a set, for example:

${a, b, c}$
${a, b, -c}$
${a, -b, c}$
${a, -b, -c}$
${-a, b, c}$
${-a, b, -c}$
${-a, -b, c}$
${-a, -b, -c}$

Can you describe an algorithm that creates all of these sets? Hint, consider the above algorithm and modify it slightly.

Combinations of true and false

Suppose we want to consider all possible combinations of $n$ instances of true ($T$) or false ($F$). For example, if $n = 4$, we are interested in

${F, F, F, F}$
${F, F, F, T}$
${F, F, T, F}$
${F, F, T, T}$
${F, T, F, F}$
${F, T, F, T}$
${F, T, T, F}$
${F, T, T, T}$
${T, F, F, F}$
${T, F, F, T}$
${T, F, T, F}$
${T, F, T, T}$
${T, T, F, F}$
${T, T, F, T}$
${T, T, T, F}$
${T, T, T, T}$

Can you describe an algorithm that creates all possible combinations of these two values? Again, consider the above two algorithms and modify them slightly.

These last two examples demonstrate how essentially the same algorithm can solve what appear to be significantly different problems.