C++ Exercises: Counts the number of combinations where the sum of the digits equals to given number

Last update on April 05 2025 13:34:51 (UTC/GMT +8 hours)

Digit Combinations with Given Sum

Write a C++ program that reads n digits chosen from 0 to 9 and counts the number of combinations where the sum of the digits equals the given number. Do not use the same digits in a combination.
For example, the combinations where n = 2 and s = 5 are as follows:
0 + 5 = 5
1 + 4 = 5
3 + 2 = 5

Visual Presentation:

C++ Exercises: Counts the number of combinations where the sum of the digits equals to given number

Sample Solution:

C++ Code :

#include <string.h> // Header file for string manipulation
#include <iostream> // Header file for input/output stream operations

using namespace std; // Using the standard namespace

int main()
{
    const int MAX_NUM  = 9; // Maximum number of digits
    const int MAX_NOS = 9; // Maximum number of sets
    const int MAX_SUM_VAL = 100; // Maximum sum value

    int n, s, dp[MAX_NOS + 1][MAX_NUM + 1][MAX_SUM_VAL + 1]; // Declaration of variables and an array for dynamic programming

    long long SUM_VAL = 0; // Initializing SUM_VAL as a long long variable

    memset(dp, 0, sizeof(dp)); // Initializing the 'dp' array to 0

    // Initializing dp array for base case of single digits
    for (int i = 0; i < MAX_NUM; i++)
    {
        dp[1][i][i] = 1;
    }

    // Dynamic programming to calculate the number of ways to form numbers with given sum and number of digits
    for (int N = 2; N <= MAX_NOS; N++)
    {
        for (int i = 1; i <= MAX_NUM; i++)
        {
            for (int j = 1; j <= MAX_SUM_VAL; j++)
            {
                if (j - i >= 0)
                {
                    for (int k = 0; k < i; k++)
                    {
                        dp[N][i][j] += dp[N - 1][k][j - i];
                    }
                }
            }
        }
    }

    cin >> n >> s; // Input for number of digits and required sum

    SUM_VAL = 0; // Reset SUM_VAL to 0

    // Calculating the total number of pairs satisfying the given conditions
    for (int i = 0; i <= MAX_NUM; i++)
    {
        SUM_VAL += dp[n][i][s];
    }

    // Outputting the result
    cout << "Number of digits " << n << " and Sum = " << s;
    cout << "\nNumber of pairs: " << SUM_VAL << endl;

    return 0; // Indicating successful completion of the program
}

Sample Output:

Sample Input: 2 5
Number of digits 2 and Sum = 5
Number of pairs: 3

Flowchart:

For more Practice: Solve these Related Problems:

Write a C++ program to count all unique combinations of n digits (0-9) that sum to a given value without repetition.
Write a C++ program that generates and prints all digit combinations where the sum of digits equals a specified value, ensuring no digit repeats.
Write a C++ program to determine the number of unique combinations of digits that add up to a target sum using backtracking.
Write a C++ program that accepts n and s, then finds and displays each combination of distinct digits that sum to s using recursion.

C++ Code Editor:

Previous: Write a C++ program which reads a sequence of integers and prints mode values of the sequence. The number of integers is greater than or equals to 1 and less than or equals to 100.
Next: Write a C++ program that accepts sales unit price and sales quantity of various items and compute total sales amount and the average sales quantity. All input values must greater than or equal to 0 and less than or equal to 1,000, and the number of pairs of sales unit and sales quantity does not exceed 100. If a fraction occurs in the average of the sales quantity, round the first decimal place.