Digit Sum - Problem Statement

Count numbers in $[L, R]$ whose digit sum equals $S$. Classic digit DP with sum tracking. State: $(pos, tight, currentSum)$.

Transition: try each digit, add to $currentSum$, check against $S$ at the end. improvement: if $currentSum > S$, prune. At position $pos$, max remaining sum is $9 \cdot (n - pos)$. If $currentSum + maxRemaining < S$, prune. Answer = $count(R) - count(L-1)$. Handle $L = 0$ carefully.