Numbers with Given Digit Sum

Problem Overview

Count n-digit numbers whose digits sum to sum (no leading zero).

Intuition

Count n-digit numbers whose digits sum to sum (no leading zero). That is classic digit DP: ways(n, rem) = number of ways to place n more digits so their values add to rem. Digits are filled from least-significant toward the most-significant; when only one digit remains it is the leading digit, so 0 is forbidden.

Algorithm

1Memoize helper(n, rem) over remaining digits and remaining sum.
2Base: n == 0 → return 1 if rem == 0 else 0; rem < 0 → 0.
3Otherwise try digit j = 0 … 9: if n == 1 and j == 0 skip (leading zero); else add helper(n−1, rem−j).
4Cache the result in dp[n][rem].
5Return helper(n, sum), or −1 when the count is 0.

Example Walkthrough

Input: n = 2, sum = 3

1. Need two-digit numbers with digit sum 3 and no leading zero.
2. Pairs (MSD, LSD): (1,2) → 12, (2,1) → 21, (3,0) → 30.
3. (0,3) would be “03”, rejected when the last remaining digit (MSD) tries 0.
4. Total ways = 3.

Output: 3

Common Pitfalls

• Skip 0 only when n == 1 (MSD), not for every digit — inner digits may be zero.
• Return −1 when there are zero ways, not 0 (problem convention).
• Memoize with −1 sentinel; otherwise overlapping subproblems recompute exponentially.
• If sum > 9*n or sum < 1 (for n≥1 with no leading zero), answer is often −1 — DP handles this naturally.

Numbers with Given Digit Sum.java

Java

// Approach: DP memoization — helper(n, sum) = ways to fill n remaining digits with digit-sum
// sum. Try digits 0–9; when only 1 digit left (MSD), skip 0 to ban leading zeros. Return -1 if 0.
// Time: O(n * sum) Space: O(n * sum)

class Solution {

    public int countWays(int n, int sum) {
        int[][] dp = new int[n + 1][sum + 1];
        // fill dp array with -1
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < sum + 1; j++) {
                dp[i][j] = -1;
            }
        }
        int res = helper(n, sum, dp);
        return res == 0 ? -1 : res;
    }

    private int helper(int n, int sum, int[][] dp) {

        if (n == 0) {
            if (sum == 0) {
                return 1;
            }
            return 0;
        }

        if (sum < 0) {
            return 0;
        }

        if (dp[n][sum] != -1) {
            return dp[n][sum];
        }

        int res = 0;

        for (int j = 0; j <= 9; j++) {
            // n-digit number cannot have leading zeros
            if (n == 1 && j == 0) {
                continue;
            }
            res = res + helper(n - 1, sum - j, dp);
        }

        return dp[n][sum] = res;

    }
};

Was this solution helpful?