Bitmask and Tree DP

Every DP state so far has been a prefix, a grid cell, or a range — always built on top of an array index. Two more shapes break out of that mold entirely: a bitmask, where the state is which subset of items has been used, encoded as the bits of an integer; and a tree, where there’s no table at all — the recursive call stack itself is the DP, with each node combining answers already computed for its children.

What you’ll learn

• How to represent a subset as the bits of an integer, and the three bit tricks (|, &, 1 << i) every bitmask DP relies on.
• Traveling Salesman (small n) as dp[mask][i] — the classic $O(2^n \cdot n^2)$ bitmask DP.
• Why bitmask DP’s state space explodes exponentially and where its practical ceiling is.
• Tree DP: post-order DFS where each call returns what its parent needs, no explicit table required.
• House Robber III, Diameter of Binary Tree, and Maximum Independent Set on a general tree — three problems built on the same “combine children, then decide” shape.

The cue

You are looking at bitmask or tree DP when…

Bitmask DP — the state is a set:

• The constraints say n <= 20 (or 12, or 16). That number is not arbitrary: $2^{20}$ is about a million, and a bound that small is the problem telling you it expects exponential work in n.
• The answer depends on which items have been used, not how many — assignment, matching, covering, ordering with arbitrary dependencies.
• A greedy or 1-D DP fails because any subset of the remaining items could be the right next choice.

Tree DP — the state is a node:

• The input is a tree (or a DAG), and each node’s answer depends on its children’s.
• Every node has a local choice whose legality depends on what its children chose: rob or skip, colour or not, keep the edge or cut it.

The reframe: bitmask DP is 1-D DP where the “index” is a subset instead of a position — dp[mask] is “the best answer having already handled exactly these items”. Tree DP is DP where you never build a table at all: the post-order recursion is the fill order, because children always resolve before their parent reads them.

Reach for something else when n is large — 30 items already means $10^9$ states, so a bitmask is out and the problem wants a different structure; when the subset’s identity does not matter, only its size (that is ordinary 1-D DP with a counter); or when the graph has cycles, since tree DP’s recursion needs a DAG to terminate meaningfully.

Visual intuition

Bitmask DP indexes by subset, so it helps to see the subsets themselves enumerated as bit patterns — the mask axis of the table below is exactly this sequence:

bitsEvery subset of 3 items is a 3-bit integer, 000 through 1112^n masks · the DP's first index

000102

nums

705132

mask0 = 000subset{}found0

1def subsets(nums):2    n = len(nums)3    for mask in range(1 << n):        # 0 .. 2^n - 14        subset = [nums[i] for i in range(n)5                  if mask & (1 << i)]  # bit i set ⇒ take nums[i]6        yield subset

n3subsets8

setupThere are 2^3 subsets and 2^3 numbers representable in 3 bits, so the two can be put in correspondence: treat each integer's bits as "take this element or not". That turns recursion into a flat loop, which is why bitmask enumeration is the standard trick for small n.

Play‹›1/10⟲

Bit i set means item i is included. That is the whole encoding: dp[mask] indexes this list, `mask | (1 << i)` moves down it, and `(1 << n) - 1` is the last row. For n = 20 this list has about a million entries -- which is precisely why the constraints say n <= 20.

Tree DP builds no table at all. The post-order recursion is the fill order, and each call returns the summary its parent needs:

treePost-order: every child resolves before its parent reads itthe recursion IS the table

1def diameter(root):2    best = 03    def height(node):4        nonlocal best5        if node is None: return 06        l = height(node.left)7        r = height(node.right)8        best = max(best, l + r)     # path THROUGH this node9        return 1 + max(l, r)        # height reported UP10    height(root)11    return best

through0height1best0

combineAt 3: left height 0, right height 0. The longest path *through* 3 uses 0 + 0 = 0 edges, which does not beat 0. But the value returned upward is the height, 1 + max(0, 0) = 1. Keeping those two numbers distinct is the entire difficulty of this problem.

Play‹›1/6⟲

This is House Robber III's tree. Watch the order nodes are finished in -- leaves first, root last. That ordering is what makes tree DP need no explicit table: by the time a node computes its own answer, both children have already returned theirs.

Bitmask DP: state = (subset, position)

When a problem depends on which subset of up to ~20 items has been used — not their count, their specific identity — encode the subset as the bits of an integer mask. Bit i set means “item i is in the subset.” Three operations cover everything you need:

• mask | (1 << i) — add item i to the subset.
• mask & (1 << i) — test whether item i is already in the subset (non-zero means yes).
• (1 << n) - 1 — the “full” mask, every item included.

Traveling Salesman Problem (small n)

Visit every city exactly once, starting and ending at city 0, minimizing total travel distance. Brute force tries all (n-1)! orderings; bitmask DP collapses that to 2^n subsets: dp[mask][i] is the cheapest way to start at city 0, visit exactly the cities in mask, and end at city i.

$$dp[mask][i] = \min_{j \in mask,\ j \neq i} \Big( dp[mask \setminus \{i\}][j] + dist[j][i] \Big)$$

tsp_bitmask.py

def tsp(dist):
    n = len(dist)
    full_mask = (1 << n) - 1
    # dp[mask][i] = min cost to start at city 0, visit exactly the cities in
    # mask, and end at city i (i must be a member of mask).
    dp = [[float("inf")] * n for _ in range(1 << n)]
    dp[1][0] = 0   # mask = {0}, currently at city 0, cost so far = 0
 
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == float("inf") or not (mask & (1 << i)):
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue                       # j already visited in this mask
                new_mask = mask | (1 << j)
                new_cost = dp[mask][i] + dist[i][j]
                if new_cost < dp[new_mask][j]:
                    dp[new_mask][j] = new_cost
 
    # close the tour: return from the last city back to city 0
    return min(dp[full_mask][i] + dist[i][0] for i in range(1, n))
 
 
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print(tsp(dist))   # expect 80  (tour 0 -> 1 -> 3 -> 2 -> 0)

The assignment problem (match n workers to n tasks at minimum total cost) uses the exact same shape: dp[mask] is the min cost to assign tasks to the workers represented by mask’s set bits, trying every unused task as “the next one assigned” — one dimension instead of two, since the worker being assigned is always popcount(mask).

Bitmask DP’s state space explodes — know the ceiling

A dp[mask][i] table has 2^n * n entries. At n = 20 that’s already over 20 million cells; at n = 30 it’s billions — far beyond what memory can hold, long before the O(2^n \cdot n^2) time becomes the bottleneck. Bitmask DP is the right tool for n roughly 20 or smaller (subset problems, small TSP, assignment problems) — it is not a general substitute for polynomial DP once n grows past that.

Tree DP: the call stack is the table

A tree has no natural “index” to loop over, so tree DP skips the explicit table entirely: a post-order DFS visits every node, and each call returns whatever value(s) its parent needs to make its own decision. Because children are always resolved before their parent uses them, the recursion itself enforces the correct DP order.

House Robber III

Rob houses arranged in a binary tree; robbing a node forbids robbing its direct children (no such restriction on grandchildren). Each call returns two numbers: the best total if this node is robbed, and the best total if it’s skipped.

$$rob(node) = node.val + skip(left) + skip(right)$$ $$skip(node) = \max\big(rob(left), skip(left)\big) + \max\big(rob(right), skip(right)\big)$$

house_robber_iii.py

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def rob(root):
    def dfs(node):
        if node is None:
            return 0, 0   # (best if robbed, best if skipped) for an empty subtree
 
        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)
 
        rob_this = node.val + left_skip + right_skip       # can't rob a robbed child
        skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)
 
        return rob_this, skip_this
 
    rob_root, skip_root = dfs(root)
    return max(rob_root, skip_root)
 
 
#        3
#       / \
#      2   3
#       \   \
#        3   1
tree = Node(3, Node(2, None, Node(3)), Node(3, None, Node(1)))
print(rob(tree))   # expect 7  (rob 3 + 3 + 1, skipping the two 2/3 nodes on the second level)

Diameter of Binary Tree

The diameter is the longest path between any two nodes, measured in edges — not necessarily through the root. Each call returns its subtree’s height, but along the way it also updates a running best for “the longest path passing through this node”:

$$\text{height}(node) = 1 + \max\big(\text{height}(left),\ \text{height}(right)\big)$$ $$\text{best} = \max\big(\text{best},\ \text{height}(left) + \text{height}(right)\big) \quad \text{at every node}$$

diameter_of_binary_tree.py

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def diameter(root):
    best = [0]   # mutable cell so the nested function can update it
 
    def height(node):
        if node is None:
            return 0
        left_h = height(node.left)
        right_h = height(node.right)
        best[0] = max(best[0], left_h + right_h)     # longest path THROUGH this node
        return 1 + max(left_h, right_h)
 
    height(root)
    return best[0]
 
 
#        1
#       / \
#      2   3
#     / \
#    4   5
tree = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(diameter(tree))   # expect 3  (path 4 -> 2 -> 5, or 4 -> 2 -> 1 -> 3)

diagram Tree DP: DFS returns bubble up from leaves before the parent decides mermaid

  graph BT
    N4["4 (leaf: height 1)"] --> N2["2 (height 2, best updated to 1+1=2)"]
    N5["5 (leaf: height 1)"] --> N2
    N3["3 (leaf: height 1)"] --> N1["1 (height 3, best updated to 2+1=3)"]
    N2 --> N1

Binary Tree Maximum Path Sum is the same shape as diameter, but summing node values instead of counting edges — and clamping each child’s contribution at max(0, subtree_sum), since a negative subtree should simply be excluded from the path rather than dragging the sum down.

Maximum Independent Set on a general tree

House Robber III generalizes cleanly to any tree given as an adjacency list: each node still returns (include, exclude), but now sums over every child instead of just two.

max_independent_set_tree.py

def max_independent_set(n, edges, weight):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    def dfs(node, parent):
        include = weight[node]     # take this node -- children must be excluded
        exclude = 0                 # skip this node -- children are free either way
 
        for child in graph[node]:
            if child == parent:
                continue
            child_include, child_exclude = dfs(child, node)
            include += child_exclude
            exclude += max(child_include, child_exclude)
 
        return include, exclude
 
    include_root, exclude_root = dfs(0, -1)
    return max(include_root, exclude_root)
 
 
# tree:      0
#           / \
#          1   2
#         / \
#        3   4
edges = [(0, 1), (0, 2), (1, 3), (1, 4)]
weight = [1, 1, 1, 1, 1]
print(max_independent_set(5, edges, weight))   # expect 3  (e.g. {2, 3, 4})

Dry run

TSP on four cities, with the distance matrix from the code above. dp[mask][i] is the cheapest route that starts at 0, has visited exactly mask, and currently sits at i. Reachable entries only:

mask	cities visited	dp[mask][·]
0001	0	dp[·][0] = 0 — the seed
0011	1	dp[·][1] = 10
0101	2	dp[·][2] = 15
1001	3	dp[·][3] = 20
0111	2	dp[·][1] = 50 (via 2), dp[·][2] = 45 (via 1)
1011	3	dp[·][1] = 45 (via 3), dp[·][3] = 35 (via 1)
1111	all	dp[·][1] = 70, dp[·][2] = 65, dp[·][3] = 75

Closing the tour by returning to city 0: 70 + 10 = 80, 65 + 15 = 80, 75 + 20 = 95. The answer is 80 — the tour 0 → 1 → 3 → 2 → 0.

• The second index is not decoration. dp[0111] holds two different values, 50 and 45, because “visited 2, standing at 1” and “standing at 2” have different futures. Drop the position and the recurrence cannot be written: you would not know which distance to add next.
• Two distinct tours tie at 80. 0→1→3→2→0 and its reverse. Symmetric distance matrices always produce this pair, which is a useful sanity check — and the reason the closing min ranges over i from 1, never 0.
• Only 15 of the 64 (mask, i) cells are ever finite. Every reachable state must have bit i set in mask and bit 0 set (the tour starts at 0), so three quarters of the table is structurally unreachable. Iterating masks in increasing numeric order is enough to guarantee correctness, because adding a city only ever increases the mask — that is the topological order, for free.
• The bound is $O(2^n \cdot n^2)$, not $(n-1)!$. At $n = 4$ that is 6 permutations versus 64 cells, so the DP looks worse; at $n = 15$ it is $87$ billion permutations versus about $7.4$ million cells. That crossover is the whole point.

Tree DP — House Robber III on the tree [3,2,3,null,3,null,1]. Post-order, so leaves resolve first. Each row is one dfs return:

node	children’s (rob, skip)	rob_this = val + left_skip + right_skip	skip_this = max(L) + max(R)
leaf 3 (under 2)	(0,0), (0,0)	3	0
2	left (0,0), right (3,0)	2 + 0 + 0 = 2	0 + max(3,0) = 3
leaf 1 (under right 3)	(0,0), (0,0)	1	0
right 3	left (0,0), right (1,0)	3 + 0 + 0 = 3	0 + max(1,0) = 1
root 3	left (2,3), right (3,1)	3 + 3 + 1 = 7	max(2,3) + max(3,1) = 6

Answer max(7, 6) = **7** — rob the root and both grandchildren, skipping the middle level.

• Node 2 prefers to be skipped: skip_this = 3 beats rob_this = 2, because its child is worth more than it is. Returning only a single “best” number would lose that distinction — the parent needs skip specifically, since it plans to rob itself.
• The pair is the state. This is 1-D DP’s (take, skip) idea moved onto a tree: the parent’s legality constraint is expressed by which of the two numbers it reads, not by any bookkeeping.
• No table exists. The “fill order” is post-order traversal, and correctness comes from the recursion, not from a loop ordering you had to get right.

Time and space complexity

Problem	Time	Space
Bitmask DP (TSP, assignment)	$O(2^n \cdot n^2)$	$O(2^n \cdot n)$
Tree DP (House Robber III, diameter, max independent set)	$O(n)$	$O(h)$ recursion depth

When to use it

• Bitmask DP: the problem depends on which specific subset of a small number of items (roughly $n \le 20$) has been chosen or visited — TSP, assignment problems, “partition into K equal-sum subsets.”
• Tree DP: the input is literally a tree (or reduces to one), and the answer at each node depends on combining results already computed for its children — include/exclude decisions, path sums, subtree heights.
• If a “subset” problem’s n is too large for 2^n to fit in memory, look for a smaller state (a count, a sum, a boolean) instead of the whole subset — that’s usually a sign a different DP shape from earlier lessons applies instead.

The variant map

Problem	State	The one thing that changes
TSP (small n)	dp[mask][i] — visited set + current city	the second index is mandatory; without it there is no “where am I” to extend from
LC 847 Shortest Path Visiting All Nodes	(node, mask) in a BFS queue	unweighted, so BFS over the state space beats a DP table — see BFS with extra state
LC 864 Shortest Path to Get All Keys	(cell, keys_mask)	the mask is keys collected, and the grid supplies the moves
LC 526 Beautiful Arrangement	dp[mask] — position is popcount(mask)	the position is implied by how many bits are set, so one dimension suffices
LC 1178 Number of Valid Words for Each Puzzle	mask per word	precompute a mask per word, then enumerate submasks of each puzzle
LC 698 Partition to K Equal Sum Subsets	dp[mask] + current bucket sum	the bucket sum is derivable from the mask, so it need not be stored
LC 1125 Smallest Sufficient Team	dp[mask] → set of people	store the witness alongside the cost when the answer is a set, not a number
Submask enumeration	sub = (sub - 1) & mask	iterates every submask of mask in $O(3^n)$ total across all masks, not $O(4^n)$
LC 337 House Robber III	(rob, skip) per node	the pair is the state
LC 543 Diameter	height returned, best recorded	split-brain: return one thing, record another
LC 124 Max Path Sum	height with max(0, …) clamp	negative subtrees are dropped rather than extended
LC 968 Binary Tree Cameras	three states per node	covered-by-self / covered-by-child / not-covered — the same shape with a wider tuple
Tree knapsack	dp[node][budget]	a 2-D DP per node, merged child by child

The two bit tricks worth memorising

popcount — bin(mask).count("1") in Python, or mask.bit_count() on 3.10+. It turns “how many items are used” into an $O(1)$ lookup, which is what lets LC 526 drop the position dimension entirely.

Submask enumeration — sub = mask; while sub: … ; sub = (sub - 1) & mask. Iterating every submask of every mask costs $O(3^n)$ in total, not $O(4^n)$, because each bit is independently in-sub / in-mask-only / out. That distinction is what makes set-cover style problems feasible at n = 16.

Interview follow-ups

They ask	What they’re checking	The answer
“The constraints say n <= 20. What does that tell you?”	Reading the problem	That exponential-in-n is expected: $2^{20} \approx 10^6$ states is fine. A bound that small is almost always a bitmask hint, in the same way n <= 500 hints at $O(n^3)$
“Why does TSP’s state need the current city as well as the mask?”	The core of the recurrence	Because the cost of extending depends on where you are standing. dp[mask] alone cannot tell you which distance to add next. The mask says what is done; the index says where you are
“What is the complexity, and why is it better than brute force?”	Comparing exponentials	$O(2^n \cdot n^2)$ against $O((n-1)!)$. At n = 15 that is ~7 million versus ~87 billion. Both are exponential; only one finishes
“n is now 30”	Boundaries	$2^{30}$ states is a billion — out of reach. The problem must have different structure: a tree instead of a general graph, a greedy exchange argument, or meet-in-the-middle at $O(2^{n/2})$
“Why does tree DP need no table?”	Understanding the fill order	Because post-order traversal is a valid fill order: children resolve before their parent reads them. The recursion enforces the dependency that a table’s loop order would have to encode manually
“Why return a pair in House Robber III?”	The state design	Because the parent’s options depend on which choice the child made. Returning only the best number loses the information the parent needs — node 2 in the trace prefers being skipped (3) over being robbed (2)
“Now the tree is a general graph with cycles”	Boundaries again	Tree DP breaks: a node’s subtree is no longer well defined and the recursion may not terminate. You need SCC condensation first, or a different formulation entirely
“Enumerate all submasks of a mask”	A specific idiom	sub = mask; while sub: process(sub); sub = (sub - 1) & mask — and note the total over all masks is $O(3^n)$, not $O(4^n)$

Practice — real LeetCode problems

Two ways to escape the array. Tree DP replaces the index with a node and the table with the call stack, returning a tuple of states per node. Bitmask DP packs a set into an integer, which only works because the constraints keep the number of elements around 20.

LC 337 — House Robber III · Medium

Problem. The houses form a binary tree. You cannot rob two directly connected houses. Return the maximum you can take.

Constraints. 1 <= number of nodes <= 10**4, 0 <= node.val <= 10**4.

Examples. [3,2,3,null,3,null,1] gives 7 (3 + 3 + 1) · [3,4,5,1,3,null,1] gives 9 (4 + 5)

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Tree DP: the recursion is the table, evaluated in post-order because a node’s answer needs its children’s.

The reason a single number per node fails is worth stating precisely. If dfs returned only “the best for this subtree”, the parent could not tell whether that best plan robbed the child — and that is exactly the fact the parent needs. Returning both conditional values fixes it. This is the same idea as the take/skip pair in LC 198, lifted from a line to a tree.

Time $O(n)$, one visit per node. Space $O(h)$ for the stack, which is $O(n)$ on a degenerate tree — and at n = 10**4 a path-shaped tree will blow Python’s default recursion limit of 1000. Say so; on LeetCode it happens to pass, but an interviewer may want the iterative post-order or an explicit sys.setrecursionlimit.

• robbed must use the children’s skipped values, never their maxima. Using max there is the bug that silently robs adjacent nodes.
• skipped takes each child’s own max independently. Skipping a node imposes no constraint on either child, and the two children never constrain each other.
• (0, 0) for None makes the leaves work with no special case.
• [4,1,null,2,null,3] is a left-leaning path 4-1-2-3, and the answer is 7 — the two ends, 4 and 3. Path-shaped trees are what catch a recurrence that quietly assumes two children.
• The naive memo on (node, parent_robbed) also works and is a fine answer; the tuple version just needs no dictionary.

Follow-ups you should expect: “Which houses?” — return the chosen sets, or re-descend making the same comparisons. “An n-ary tree?” — sum skipped over all children for the robbed case, and sum the per-child maxima for the skipped case. “A general graph?” — maximum weight independent set, NP-hard; trees are tractable because there is exactly one path between any two nodes. “Iteratively?” — post-order with an explicit stack, or process nodes in reverse BFS order. “Binary Tree Cameras (LC 968)?” — the same tree-DP shape with three states instead of two.

LC 847 — Shortest Path Visiting All Nodes · Hard

Problem. Given an undirected connected graph as an adjacency list, return the length of the shortest walk that visits every node. You may start and stop anywhere, and may revisit nodes and edges.

Constraints. 1 <= n <= 12, the graph is connected, no self-loops or duplicate edges.

Examples. [[1,2,3],[0],[0],[0]] gives 4 · [[1],[0,2,4],[1,3,4],[2],[1,2]] gives 4

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Read the constraint first. n <= 12 gives $2^{12} = 4096$ subsets, and $12 \times 4096 = 49152$ states — tiny. Whenever n is around 12 to 20 and the problem is about sets, the intended solution is almost always a bitmask.

The key modelling insight is that the node alone is not a state. You may need to walk back through a node you have already visited, so visited cannot be a plain per-node flag; it is part of the state. (node, mask) can be reached at most once usefully, and since every edge has weight 1, BFS over that state graph gives shortest distances directly — no Dijkstra needed.

Time $O(2^n \cdot n^2)$. Space $O(2^n \cdot n)$.

• Seeding all n starts at distance 0 is how “start anywhere” is encoded. A single-source BFS from node 0 answers a different, harder question.
• (1 << i) as the initial mask — you have visited your own starting node.
• n = 1 must return 0: the seed state already has the full mask, and the check happens on dequeue, before any edge is walked. The [[]] case verifies exactly this, and it is why the mask test belongs at the top of the loop body rather than when enqueueing.
• Marking seen at enqueue time, not dequeue time, is what keeps the queue from blowing up with duplicates. This is standard BFS hygiene and still worth saying.
• The return 0 at the end is unreachable for connected input — but write it rather than falling off the function.

Follow-ups you should expect: “How is this different from Travelling Salesman?” — TSP forbids revisiting, so it is a Held-Karp DP over (mask, last) minimising edge weights; here revisiting is allowed, which is what makes plain BFS correct. “Weighted edges?” — Dijkstra over the same state space. “Return the walk?” — store a parent per state and walk back. “n = 40?” — $2^{40}$ states is out of reach; that is the meet-in-the-middle or approximation regime. “Must return to the start?” — add the closing edge, and the start node must then be part of the state.

LC 968 — Binary Tree Cameras · Hard

Problem. Place cameras on tree nodes. A camera monitors its own node, its parent and its immediate children. Return the minimum number of cameras needed so every node is monitored.

Constraints. 1 <= number of nodes <= 1000, all node values are 0.

Examples. [0,0,null,0,0] gives 1 · [0,0,null,0,null,0,null,null,0] gives 2

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Minimum vertex cover’s cousin — a dominating set on a tree — and the tree structure is what makes a greedy bottom-up pass optimal.

The exchange argument, which is the part to say out loud: a camera on a leaf covers the leaf and its parent, while a camera on that parent covers the leaf, the parent and the parent’s parent. So moving any leaf camera up to its parent never covers less. Therefore an optimal solution exists that places cameras only when a child is otherwise exposed — which is exactly the rule the code implements. Place as late as possible, and only under duress.

The three states are the minimum information a parent needs. Two would not do: “covered” has to be split by whether a camera lives here, because a child’s camera covers the parent for free while a merely-covered child does not.

Time $O(n)$. Space $O(h)$.

• None returns 1, not 0. If missing children counted as uncovered, every leaf would demand its own camera and you would roughly double the count.
• The order of the two checks matters. Exposed children are an obligation and must be handled first; a child’s camera is only a bonus.
• The root needs the final check. Every other node can be rescued by its parent; the root has none, so a state of 0 there costs one more camera.
• A single node answers 1 via that root check — both children are None, which returns 1, so dfs returns 0 and the root branch fires.
• [0,0,0] — a root with two leaf children — answers 1: one camera on the root covers all three. The leaves return 0, the root is forced, and it happens to be the optimum.
• self.cameras as a counter sidesteps threading a running total through the return value. A nonlocal variable or a list of length 1 does the same job.

Follow-ups you should expect: “Prove the greedy is optimal?” — the exchange argument above; interviewers labelling this Hard mostly want that. “As an explicit DP?” — return a triple of costs per state and minimise, which is the mechanical version and generalises to weighted nodes. “Weighted cameras?” — the greedy breaks and you need that triple. “Minimum vertex cover on a tree (a camera covers only its edges)?” — the same two-state tree DP as House Robber III. “An n-ary tree?” — identical, with any(child == 0) over the children list. “A general graph?” — dominating set is NP-hard.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

9 problems

1 easy3 medium5 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○543Diameter of Binary TreeeasyThe height-plus-running-max template aboveNeetCode 150
• ○337House Robber IIImediumThe include/exclude tree DP above
• ○357Count Numbers with Unique Digitsmedium
• ○698Partition to K Equal Sum SubsetsmediumBitmask DP over which elements have been assigned to a bucket so far
• ○124Binary Tree Maximum Path SumhardDiameter's shape, summing values with negative subtrees clamped to 0NeetCode 150Blind 75LeetCode Top Interview 150
• ○847Shortest Path Visiting All Nodeshard
• ○864Shortest Path to Get All Keyshard
• ○1012Numbers With Repeated Digitshard
• ○2376Count Special Integershard

Self-check

pch.quizTag Bitmask and tree DP — self-check

1. A problem's constraints say `n <= 20`. What does that suggest?

   A That the input is trivially small and any solution works B That exponential-in-n is expected — 2^20 is about a million states, so a subset-indexed DP is affordable and probably intended C That an O(n²) solution is required D Nothing; it is an arbitrary bound
   pch.quizShowAnswer

   B — That exponential-in-n is expected — 2^20 is about a million states, so a subset-indexed DP is affordable and probably intended — Reading constraints as a hint about the intended complexity class is a real skill: n ≤ 20 suggests bitmask, n ≤ 500 suggests O(n³) interval DP, n ≤ 10^5 rules both out.

2. Why does TSP's state need the current city in addition to the visited mask?

   A To detect cycles B Because the cost of the next step depends on where you are standing — dp[mask] alone cannot tell you which distance to add C To count how many cities remain D It does not; the mask is sufficient
   pch.quizShowAnswer

   B — Because the cost of the next step depends on where you are standing — dp[mask] alone cannot tell you which distance to add — In the dry run, dp[0111] holds both 50 (standing at city 1) and 45 (standing at city 2) — same visited set, different futures. The mask says what is done; the index says where you are.

3. How does O(2^n · n²) compare with brute-force O((n-1)!) for TSP?

   A They are the same B Both are exponential, but at n = 15 the DP is about 7 million cells against roughly 87 billion permutations — only one finishes C The DP is polynomial D The factorial version is faster for all n
   pch.quizShowAnswer

   B — Both are exponential, but at n = 15 the DP is about 7 million cells against roughly 87 billion permutations — only one finishes — Note the DP is actually worse at n = 4 (64 cells versus 6 permutations). Naming where the crossover happens is more convincing than asserting the DP is simply better.

4. Why does tree DP need no explicit table?

   A Because trees are small B Because post-order traversal is itself a valid fill order — children always resolve before their parent reads them, so the recursion enforces the dependency a table's loop order would have to encode C Because each node has at most two children D Because it memoises automatically
   pch.quizShowAnswer

   B — Because post-order traversal is itself a valid fill order — children always resolve before their parent reads them, so the recursion enforces the dependency a table's loop order would have to encode — This is why 'get the loop order right' — the hard part of interval DP — simply does not arise in tree DP. It is also why cycles break it: there would be no valid order.

5. In House Robber III, why return a `(rob, skip)` pair rather than the single best value?

   A For symmetry with the array version B Because a parent that robs itself needs its children's SKIP values specifically — the single best number loses that. Node 2 in the trace has rob = 2 but skip = 3 C To avoid recursion D Because the tree may be unbalanced
   pch.quizShowAnswer

   B — Because a parent that robs itself needs its children's SKIP values specifically — the single best number loses that. Node 2 in the trace has rob = 2 but skip = 3 — It is the same (take, skip) idea as 1-D House Robber, relocated onto a tree. The legality constraint is expressed by which of the two numbers the parent reads.

6. What is the total cost of enumerating every submask of every mask, and what is the idiom?

   A O(4^n), with nested loops over all pairs B O(3^n), via `sub = mask; while sub: …; sub = (sub - 1) & mask` — each bit is independently in-sub, in-mask-only, or out C O(2^n), one pass D O(n · 2^n)
   pch.quizShowAnswer

   B — O(3^n), via `sub = mask; while sub: …; sub = (sub - 1) & mask` — each bit is independently in-sub, in-mask-only, or out — The 3^n bound is what makes set-cover and partition-into-subsets problems feasible at n = 16. Getting O(4^n) instead — by testing every mask against every other — is the difference between passing and timing out.

Recall card

• Bitmask cue — n <= 20 in the constraints, and the answer depends on which items are used, not how many.
• Encoding — bit i set = item i used. mask \| (1 << i) adds, mask & (1 << i) tests, (1 << n) - 1 is full.
• State design — dp[mask] when the position is implied (e.g. popcount(mask)); dp[mask][i] when you also need where you are, as in TSP.
• Iterate masks in increasing numeric order — adding an item only increases the mask, so that ordering is a topological order for free.
• Cost — $O(2^n \cdot n^2)$ for TSP-shaped problems. $n = 20$ is fine, $n = 30$ is not.
• Submasks — sub = (sub - 1) & mask, $O(3^n)$ across all masks.
• Tree DP — no table: post-order DFS, each call returns what its parent needs. Often a tuple: (rob, skip), (covered, uncovered), (height, best).
• Cycles break tree DP — condense SCCs first, or use a different formulation.

Recap

• Bitmask DP encodes a subset as the bits of an integer; dp[mask][i] answers “best result using exactly this subset, ending at i” — Traveling Salesman and assignment problems share this shape.
• The state space is $O(2^n)$, so bitmask DP is only practical for roughly $n \le 20$ — know that ceiling before reaching for it.
• Tree DP needs no explicit table: a post-order DFS’s return value carries whatever the parent needs, and the call stack itself enforces “children before parent.”
• House Robber III, Diameter of Binary Tree, and Maximum Independent Set all share the same “combine children, then decide include vs. exclude (or the best split)” pattern.

Between prefix DP, grid/interval DP, and bitmask/tree DP, you now have the full toolkit for recognizing and solving the overwhelming majority of DP-flavored interview and competitive-programming questions — the hard part from here is just practice: spotting which shape a new problem’s state actually needs.