Subsets as bitmasks

Number some items 0, 1, 2, …. Then any subset of them can be stored as one whole number: bit i is 1 when item i is in the subset. The operators of lesson 2 become set operations, and counting from 0 to 2ⁿ − 1 lists every subset. This is the first step towards bitmask DP (ADDP-4).

A set in one number

A number used this way is called a bitmask. With items a, b, c as places 0, 1, 2, the number 5 (101) is the subset {a, c}, and 0 is the empty subset. Every set operation is one operator:

s >> i & 1           # is item i in s?
s | (1 << i)         # add item i
s & ~(1 << i)        # remove item i
a | b                # union: in a or in b
a & b                # common part: in both
a & ~b               # in a but not in b
full = (1 << n) - 1  # all n items
full ^ s             # the items not in s
s.bit_count()        # how many items
a & b == a           # is a a subset of b?

For up to a few dozen items this is faster than a Python set, uses far less memory, and a bitmask can be a dict key directly, because it is just a number.

Every subset

n items have 2ⁿ subsets: each item is in or out, and the choices multiply. Their bitmasks are exactly the numbers 0 to 2ⁿ − 1, so for mask in range(1 << n) visits every subset once. Reading the items of each mask takes n steps, so working on every subset this way costs O(2ⁿ · n).

Often a subset’s answer can be built from a smaller subset’s answer instead. Remove the lowest item: mask ^ low, where low = mask & -mask (lesson 3), is a smaller number, so its answer is already known. The first version of the figure fills in the weight of every subset this way, with one addition each.

def subset_sums(w):
    n = len(w)
    sums = [0] * (1 << n)
    for mask in range(1, 1 << n):
        low = mask & -mask              # the lowest item's bit
        i = low.bit_length() - 1        # ... and its number
        sums[mask] = sums[mask ^ low] + w[i]
    return sums

subset_sums([5, 3, 8])   # [0, 5, 3, 8, 8, 13, 11, 16]

This is O(2ⁿ). A shorter way gives the same list: start with [0], and for each item add a copy of the list with the item’s weight added to every sum (sums += [s + v for s in sums]). After the first k items, the list holds the sums of all subsets of those k items.

Submasks

Sometimes you need every subset of one given subset: the submasks of a mask. Counting from 0 to mask and skipping the numbers with a 1 outside the mask wastes most of the steps. This loop visits only the submasks, largest first:

def submasks(mask):
    sub = mask
    while True:
        yield sub
        if sub == 0:
            break
        sub = (sub - 1) & mask

Why does it work? sub - 1 turns the lowest 1 of sub into 0 and sets every place below it to 1. Then & mask clears the places that are not in the mask. If you look only at the mask’s own places, this is exactly subtracting 1 from a smaller number. So the loop counts down through every pattern of the mask’s places, from all of them to none. The second version of the figure lists the 8 submasks of 1101.

Here 3ⁿ means 3 to the power n. Why 3? For each pair (mask, submask), each item is in one of three states: not in the mask, in the mask but not in the submask, or in both. Every pattern of n such states is one pair, so there are exactly 3ⁿ pairs. For n = 15 that is about 14 million, against about a billion for every pair of masks. Bitmask DP (ADDP-4) often loops over submasks like this.

To list only the subsets of size k, start with the k lowest items, (1 << k) - 1, and step to the next number with as many 1s (lesson 3), or use itertools.combinations(range(n), k).

Meeting in the middle

Is there a subset of 40 numbers that adds up to exactly t? There are 2⁴⁰, about a million million, subsets: far too many. But each subset is a part from the first 20 numbers plus a part from the last 20. So:

1. List the sums of all subsets of the first half: 2²⁰, about a million.
2. Put the sums of all subsets of the second half in a Python set.
3. For each sum s of the first half, check whether t − s is in the set.

That is about two million steps instead of a million million. In general, O(2ⁿ) becomes about O(2ⁿᐟ²), 2 to the power n/2: the square root of the work, paid for with the memory for one half’s sums. The method is called meeting in the middle. DYNP-8 mentioned it for the knapsack with few items. For the closest sum to t, a set is not enough: sort one half’s sums and use binary search (BSRC) to find the best partner for each sum of the other half. That is BITS-P5.

How far subsets go

In Python, simple work on 2²⁰ (about a million) subsets takes under a second. 2²⁵ (about 33 million) takes many seconds, and 2³⁰ (about a billion) is out of reach. So plain subset listing suits about 20 items, and meeting in the middle about 40.

Now try BITS-P5, The closest subset sum.