enumerating all subsets

You have a shelf of n items and want to consider every possible selection: take none, take all, take just the odd ones, take any mix. The collection of all those selections is the powerset, and it has exactly 2^n members because each item independently faces one yes/no decision — in or out. Listing them all, once each, is enumerating all subsets.

The cleanest way to see this is the bitmask trick. Number the items 0 to n-1. Any subset corresponds to an n-bit binary number where bit i is 1 if item i is included. So the subsets are in one-to-one correspondence with the integers 0, 1, 2, ..., 2^n - 1: just count from 0 up to 2^n - 1, and for each integer mask read off its bits to recover the subset. For n = 3 the masks 000, 001, 010, 011, 100, 101, 110, 111 give the empty set, {0}, {1}, {0,1}, {2}, {0,2}, {1,2}, {0,1,2}. This is automatically complete and duplicate-free because the integers from 0 to 2^n - 1 are each hit exactly once. Alternatively, a recursive decision tree branches twice at each item (skip it / take it), and its 2^n leaves are the subsets — the same enumeration, viewed as depth-first search.

Subset enumeration is the workhorse behind 0/1 knapsack, subset-sum, set cover by brute force, and any problem phrased as choose a subset satisfying some property. Generating one subset takes time proportional to n (to read its bits or copy the chosen items), so the total work is Theta(n * 2^n) — fine for n up to about 20-25, hopeless beyond. When n is larger, you do not enumerate all subsets; you switch to dynamic programming, meet-in-the-middle, or pruning.