Count N-Digit Numbers with Given Digit Sum Using Dynamic Programming

Introduction

Given two integers:

n = number of digits
sum = required sum of digits

Find the number of n-digit positive integers whose digits add up to the given sum.

Important Rules

The first digit cannot be 0.
If no such number exists, return -1.

Example 1

Input

Code

n = 2
sum = 2

Possible 2-digit numbers:

Number	Digit Sum
11	2
20	2

Output

Code

Example 2

Input

Code

n = 1
sum = 10

A single digit can only be between 0 and 9.

Output

Code

-1

Example 3

Input

Code

n = 2
sum = 10

Possible numbers:

Code

Output

Code

Brute Force Approach

A straightforward solution is:

Generate all possible n-digit numbers.
Calculate the digit sum of each number.
Count numbers whose digit sum equals the required sum.

Complexity

For 9-digit numbers:

Code

10^9 possibilities

This is far too large to process within reasonable time limits.

We need a more efficient solution.

Dynamic Programming Approach

Instead of generating every number, we construct the answer digit by digit.

DP State

Let:

Code

dp[i][j]

represent:

Number of i-digit numbers whose digit sum is j.

For example:

Code

dp[2][5]

means:

Number of 2-digit numbers having digit sum 5.

Why Dynamic Programming Works

Suppose we already know:

Code

dp[2][7]

Now we want:

Code

dp[3][10]

The last digit can be:

Code

0, 1, 2, ..., 9

Case 1: Last Digit = 3

Then the first two digits must contribute:

Code

10 - 3 = 7

which is stored in:

Code

dp[2][7]

Case 2: Last Digit = 5

Need:

Code

dp[2][5]

Case 3: Last Digit = 8

Need:

Code

dp[2][2]

Therefore:

Code

dp[3][10]
=
dp[2][10]
+
dp[2][9]
+
dp[2][8]
+
...
+
dp[2][1]

This becomes our DP transition.

DP Formula

For every possible digit from 0 to 9:

Code

dp[i][s]
=
Σ dp[i−1][s−digit]

or:

Java

dp[i][s] += dp[i - 1][s - digit];

provided:

Code

s >= digit

Initialization

The first digit cannot be zero.

Possible first digits:

Code

1, 2, 3, ..., 9

Therefore:

Java

for (int d = 1; d <= 9; d++) {
    dp[1][d] = 1;
}

Meaning:

One-digit number with sum 1 → only 1
One-digit number with sum 2 → only 2
...
One-digit number with sum 9 → only 9

DP Table Example

Suppose:

Code

n = 2
sum = 4

Initial table:

Sum	0	1	2	3	4
dp[1]	0	1	1	1	1

Now compute:

Code

dp[2][4]

Last digit can be:

Code

0, 1, 2, 3, 4

Therefore:

Code

dp[2][4]
=
dp[1][4]
+
dp[1][3]
+
dp[1][2]
+
dp[1][1]
+
dp[1][0]

Code

=
1 + 1 + 1 + 1 + 0
=
4

Valid numbers:

Code

Exactly 4 numbers.

Complete Code

Java

class Solution {
    public int countWays(int n, int sum) {

        // Impossible case
        if (sum > 9 * n || sum < 1)
            return -1;

        int[][] dp = new int[n + 1][sum + 1];

        // Base Case
        for (int d = 1; d <= 9 && d <= sum; d++) {
            dp[1][d] = 1;
        }

        // Fill DP table
        for (int i = 2; i <= n; i++) {

            // Current required sum
            for (int s = 0; s <= sum; s++) {

                // Current digit
                for (int d = 0; d <= 9; d++) {

                    if (s >= d) {
                        dp[i][s] += dp[i - 1][s - d];
                    }
                }
            }
        }

        return dp[n][sum] == 0 ? -1 : dp[n][sum];
    }
}

Code Explanation

Step 1

Java

if (sum > 9 * n || sum < 1)
    return -1;

Maximum possible digit sum is:

Code

9 × n

Example:

Code

n = 2

Maximum sum:

Code

If:

Code

sum = 20

No valid number exists.

Return:

Code

-1

Step 2

Java

int[][] dp = new int[n + 1][sum + 1];

Create a DP table.

Rows → Number of digits
Columns → Digit sums

Step 3

Java

for (int d = 1; d <= 9 && d <= sum; d++) {
    dp[1][d] = 1;
}

Initialize one-digit numbers.

Example:

Code

dp[1][5] = 1

because:

Code

is the only one-digit number with digit sum 5.

Step 4

Java

for (int i = 2; i <= n; i++)

Build solutions for:

2 digits
3 digits
...
n digits

Step 5

Java

for (int s = 0; s <= sum; s++)

Try every possible required digit sum.

Step 6

Java

for (int d = 0; d <= 9; d++)

Try every possible digit at the current position.

Step 7

Java

if (s >= d)

Example:

Need:

Code

sum = 4

Cannot place:

Code

digit = 7

because:

Code

4 - 7 < 0

So skip it.

Step 8

Java

dp[i][s] += dp[i - 1][s - d];

This is the key DP transition.

Suppose:

Code

Need:
3 digits
sum = 8

If the last digit is:

Code

then previous digits must contribute:

Code

8 - 5 = 3

So we add:

Code

dp[2][3]

Repeat this for every digit from 0 to 9.

Step 9

Java

return dp[n][sum] == 0 ? -1 : dp[n][sum];

If no valid number exists:

Code

return -1

Otherwise:

Code

return count

Dry Run

Input

Code

n = 2
sum = 2

Initial DP

Code

dp[1][1] = 1
dp[1][2] = 1

Now compute:

Code

dp[2][2]

Try Every Last Digit

Digit = 0

Code

Need dp[1][2]
=
1

Digit = 1

Code

Need dp[1][1]
=
1

Digit = 2

Code

Need dp[1][0]
=
0

All larger digits are ignored.

Total:

Code

1 + 1 = 2

Valid numbers:

Code

11
20

Answer

Code

Complexity Analysis

Time Complexity

There are three nested loops:

n digits
sum possible sums
10 possible digits

Therefore:

Code

O(n × sum × 10)

Since 10 is constant:

Code

O(n × sum)

Space Complexity

The DP table stores:

Code

(n + 1) × (sum + 1)

values.

Therefore:

Code

O(n × sum)

Summary

The brute-force solution requires checking every n-digit number, which quickly becomes infeasible for larger values of n. Dynamic Programming provides an efficient alternative by building solutions digit by digit and reusing previously computed results. By defining dp[i][s] as the number of i-digit numbers whose digit sum equals s, we can compute the answer in O(n × sum) time and O(n × sum) space. This approach efficiently counts all valid n-digit numbers while respecting the constraint that the first digit cannot be zero.