Digit DP — Counting Numbers ≤ N with Digit Sum = S

Build the number digit by digit, most significant first. At each position the tight branch is capped at N[pos]; the free branch allows all digits. Counts bubble up from the leaves.

step 0

Bound N & the candidate being built

Bound N digits (position highlighted):
Candidate so far (tight / free):
running digit sum 0 / target 3 tight started

Tight branch

digit capped at N[pos]

Free branch

digit ∈ 0..9 (all allowed)
tight (capped by N) free (below N) valid leaf

Accumulating counts

valid completions found so far0
leaves examined0
memo (free states) reused0
f(N) so far = 0
Recursion stack (top = current frame):
Press Step to begin. We count integers in [0, N] whose digits sum to exactly S, by exploring digit choices position by position. The tight flag keeps us ≤ N.
Self-contained visualization. Running example: count numbers in [0, N] with digit sum = S. A leaf is reached at the last position; it is valid iff the accumulated digit sum equals S. Free (tight=false) states are memoized; tight states are unique per N and never cached. See junior.md and professional.md for the tight-flag decomposition proof.