Track a tiny set of visited items using the 0s and 1s of a single integer.
When solving problems like the Traveling Salesperson (TSP) or job assignments, you need to know exactly which subset of items you have visited so far. Passing around a Set or a List in DP is too slow.
Instead, if N is small (usually ≤ 20), we can represent the subset as a Bitmask. The 0th bit is 1 if item 0 is visited, the 1st bit is 1 if item 1 is visited, etc. To add item j, we do a bitwise OR: mask | (1 << j).
def solve(mask):
# Base case: all N items visited (mask is 11...1)
if mask == (1 << N) - 1:
return 0
for i in range(N):
# Check if i-th bit is NOT set
if not (mask & (1 << i)):
# Set the bit: mask | (1 << i)
new_mask = mask | (1 << i)
cost = do_something() + solve(new_mask)
ans = min(ans, cost)
return ans