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

C++ Basic: Exercise-72 with Solution

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:

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:

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.