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

C++ Basic: Exercise-72 with Solution

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

Pictorial Presentation:

Sample Solution:

C++ Code :

#include <string.h>
#include <iostream>
 
using namespace std;
 
int main()
{
    const int MAX_NUM  = 9;
    const int MAX_NOS = 9;
    const int MAX_SUM_VAL = 100;
 
    int n, s, dp[MAX_NOS + 1][MAX_NUM + 1][MAX_SUM_VAL + 1];
 
    long long SUM_VAL = 0;
 
    memset(dp, 0, sizeof(dp));
 
    for (int i = 0; i < MAX_NUM; i++)
    {
        dp[1][i][i] = 1;
    }
 
    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;
 
      SUM_VAL = 0;
 
        for (int i = 0; i <= MAX_NUM; i++)
        {
            SUM_VAL += dp[n][i][s];
        }
 
        cout << "Number of digits " << n << " and Sum = " << s;
        cout << "\nNumber of pairs: " <<SUM_VAL << endl;
  
 
    return 0;
}

Sample Output:

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

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

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.