Brute Force over Subsets¶

In one sentence

\(n\) items, each either taken or not, give \(2^n\) choices. Write each choice as an \(n\)-bit number and loop over range(1 << n). Fine up to \(n \approx 20\).

Where we are

25 Oct: choose / skip DFS on a knapsack, the same thing as a for mask loop, bit shifts, and 1097B as the example.

1. Choose or skip, with DFS¶

When we have no DP idea for a knapsack, we can still try every choice: for item k, either take it or skip it, and recurse on k + 1.

def dfs(k, val_sum, weight_sum):
    if k == n:
        if weight_sum <= cap:
            return val_sum
        return 0

    res = 0
    res = max(res, dfs(k + 1, val_sum + v[k], weight_sum + w[k]))
    res = max(res, dfs(k + 1, val_sum, weight_sum))
    return res

ans = dfs(0, 0, 0)

The recursion goes \(n + 1\) levels deep, and every item doubles the number of branches, so there are \(2^n\) leaves.

2. The same thing with a `for` loop¶

Each item has two states, \(0\) (skip) or \(1\) (take). Treat item \(i\) as bit \(i\) of a number. Then one choice for all \(n\) items is one \(n\)-bit number, called a mask:

items taken (n = 3)	mask in binary	mask
none	`000`	0
item 0	`001`	1
items 0 and 2	`101`	5
all	`111`	7 = \(2^3 - 1\)

So every choice is one integer from \(0\) to \(2^n - 1\), and for mask in range(1 << n) visits all of them.

Shifts¶

1 << n is left shift: move the \(1\) left by \(n\) places and fill with zeros. 1 << n \(= 2^n\).
x >> i is right shift: move everything right by \(i\) places; the lowest \(i\) bits are dropped.

Is item `i` in the mask?¶

Two ways, both fine:

(mask >> i) & 1: move bit \(i\) down to the last place, then keep only that bit.
mask & (1 << i): build a number with only bit \(i\) set and compare. The result is \(0\) or \(2^i\), so test it with != 0 (or just if), not == 1.

3. Example — 1097B · Petr and a Combination Lock ¶

\(n \le 15\) rotations; rotation \(i\) turns the lock by \(a_i\) degrees, clockwise or counterclockwise. Can the pointer end at \(0\)?

Bit \(i\) of the mask says the direction of rotation \(i\): \(1\) means \(+a_i\), \(0\) means \(-a_i\). The code from class:

    for mask in range(1 << n):
        # there are n bits
        total_deg = 0
        for i in range(n):
            if (mask >> i) & 1:
                total_deg += a[i]
            else:
                total_deg -= a[i]
        if total_deg % 360 == 0:
            print("YES")
            return

    print("NO")

Why % 360 and not == 0: in the last sample, \(120 + 120 + 120 = 360\), which is a full turn, so the pointer is back at \(0\).

Cost: \(2^n \cdot n = 2^{15} \cdot 15 \approx 5 \times 10^5\).

Negative numbers and `%`¶

total_deg can be negative. In Python, % always gives a result with the sign of the divisor:

z = -13
p = z % 7  # 1 or 6?
print(p)

This prints 1 (because \(-13 = 7 \cdot (-2) + 1\)). In C++, Java or C#, -13 % 7 is -6. Here it does not matter: we only compare with \(0\).

4. When to use it¶

\(n\)	\(2^n\)
20	\(\approx 10^6\)	safe
25	\(\approx 3 \times 10^7\)	upper bound, may be too slow in Python

So look for \(n \le 20\) in the constraints.

Even when \(n\) is large, the subset loop is a quick brute force for small tests. Use it as brute.py when stress testing a real solution (Stress Testing).

5. Common mistakes¶

range(2 ** n - 1)

range already stops one before its argument. range(1 << n) gives \(0 \dots 2^n - 1\), which is every mask.

mask & (1 << i) == 1

mask & (1 << i) is \(2^i\), not \(1\), when the bit is set. Use (mask >> i) & 1 or if mask & (1 << i):.

6. Practice¶

Problem	Where	Idea
1097B · Petr and a Combination Lock	25 Oct, in class	one bit per rotation: \(+a_i\) or \(-a_i\)