dp[pos][tight][sum] = count of valid completions. Base case: pos=n returns (sum==S)?1:0. Memoize only when tight=false. When tight, the valid digit range depends on the specific limit, breaking reuse. Alternative: memoize all states with limit baked in. Use dp[pos][tight][sum] where tight is binary. Trade space for simplicity. Time: O(n⋅S⋅10) where n is digit count. Space: O(n⋅S) with memoization.
Time complexity: O(logN⋅S).
Space complexity: O(logN⋅S).