DP over subsets for assignments, TSP-like problems, and state compression
Use bitmasks to represent chosen sets; transitions add/remove one element.
Use when n ≤ 20–25 and state is combinatorial over subsets.
DP states keyed by bitmask; transitions add/remove a bit (assignment/TSP). Iterate submasks/supersets when aggregating over subsets.
# Backtracking Templates
def subsets(nums):
res=[]; cur=[]
def dfs(i):
if i==len(nums): res.append(cur.copy()); return
cur.append(nums[i]); dfs(i+1); cur.pop(); dfs(i+1)
dfs(0); return res
def permutations(nums):
res=[]; used=[False]*len(nums); cur=[]
def dfs():
if len(cur)==len(nums): res.append(cur.copy()); return
for i in range(len(nums)):
if used[i]: continue
used[i]=True; cur.append(nums[i]); dfs(); cur.pop(); used[i]=False
dfs(); return resVisit all nodes with minimal path
def tsp(dist):
n=len(dist); INF=10**9
dp=[[INF]*(1<<n) for _ in range(n)]
dp[0][1]=0
for mask in range(1<<n):
for u in range(n):
if not (mask>>u)&1: continue
if dp[u][mask]==INF: continue
for v in range(n):
if (mask>>v)&1: continue
dp[v][mask|1<<v]=min(dp[v][mask|1<<v], dp[u][mask]+dist[u][v])
ans=min(dp[u][(1<<n)-1]+dist[u][0] for u in range(n))
return ansMatch tasks to agents
def assignment(cost):
n=len(cost)
from functools import lru_cache
@lru_cache(None)
def dp(i, mask):
if i==n: return 0
best=10**9
for j in range(n):
if not (mask>>j)&1:
best=min(best, cost[i][j]+dp(i+1, mask|1<<j))
return best
return dp(0,0)Iterate submasks/supersets
def or_subsets_dp(f):
# f[mask] holds initial values; compute F[mask]=sum of f[sub] over submasks
n=(len(f)-1).bit_length(); F=f[:]
for i in range(n):
for mask in range(1<<n):
if mask&(1<<i): F[mask]+=F[mask^(1<<i)]
return FSubset DP costs exponential but manageable for n≤20.
Memo tables keyed by mask.