Finding number of ways to write “n” as sum of multiple smaller numbers

This problem can be solved using multiple approaches but here we will solve this problem using Dynamic Programming and showcase how dynamic programming will make the execution super-fast.

We will go through with the same steps as mentioned in Dynamic Programming post to tackle this problem step by step for better understanding.

Let’s explain the problem,

given n, find the number of different ways to write “n” as the sum of 1, 3, 4

Example:

for n = 5, the answer is 6

5 = 1+1+1+1+1

   = 1+1+3

   = 1+3+1

   = 3+1+1

   = 1+4

   = 4+1

Let’s apply the 3 Steps rule to tackle this problem.

Step 1) Break the problem into smaller sub problem

Let’s assume S_n be the naximum number of ways to write “n” as the sum of given input (1, 3, 4)

Step 2) Solve this problem using recursion

Let’s assume

n = x1 + x2 + …. + x_k

If “x_k” = 1, then sum of rest of the terms must be equal to “n – 1”

Thus, number of ways we can get “n” using given input that ends with “1” must be equal to “S_n-1”.

Similarly,

number of ways we can get “n” using given input that ends with “3” must be equal to “S_n-3”

number of ways we can get “n” using given input that ends with “4” must be equal to “S_n-4”

Hence, the recursion function logic would resolve into following simpler formula

S_n = S_n-1 + S_n-3 + S_n-4

Step 3) Use smaller problems results to solve the bigger complex problem.

As we know,

            S₀  = 1

            S₁  = 1

            S₂  = 1

            S₃  = 2

Now, we can use Step 2) formula to calculate the number of ways to get “n” from given set of input values.

Now let’s compare the result in terms of execution time for both recursion and DP approach for solving the above problem.

#include <unistd.h>
#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;

#define FIRST_NUMBER 1
#define SECOND_NUMBER 3
#define THIRD_NUMBER 4

int calculateWaysToGetSumUsingRecursion(int sum)
{
    if(sum < 0)
    {
        return 0;
    }
    else if (sum < 3)
    {
        return 1;
    }
    else
    {
        return (calculateWaysToGetSumUsingRecursion(sum - 1) + calculateWaysToGetSumUsingRecursion(sum - 3) + calculateWaysToGetSumUsingRecursion(sum - 4));
    }
    
}

#define MAX_SUM 1000

int Ways[MAX_SUM];

void calculateWaysToGetSumUsingDP()
{
    Ways[0] = 1;
    Ways[1] = 1;
    Ways[2] = 1;
    Ways[3] = 2;

    for(int i = 4; i < MAX_SUM; i++)
    {
        Ways[i] = Ways[i - 1] + Ways[i -3] + Ways[i - 4];
    }
}

int main()
{
    // Starting the timer
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    cout<<"Inside WaysToGetSum main using recursion "<<calculateWaysToGetSumUsingRecursion(4)<<endl;
    cout<<"Inside WaysToGetSum main using recursion "<<calculateWaysToGetSumUsingRecursion(10)<<endl;
    cout<<"Inside WaysToGetSum main using recursion "<<calculateWaysToGetSumUsingRecursion(20)<<endl;
    cout<<"Inside WaysToGetSum main using recursion "<<calculateWaysToGetSumUsingRecursion(40)<<endl;
    // Stopping the timer
    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    // Starting the timer
    high_resolution_clock::time_point t3 = high_resolution_clock::now();
    calculateWaysToGetSumUsingDP();
    cout<<"Inside WaysToGetSum main using Dynamic Programming "<<Ways[4]<<endl;
    cout<<"Inside WaysToGetSum main using Dynamic Programming "<<Ways[10]<<endl;
    cout<<"Inside WaysToGetSum main using Dynamic Programming "<<Ways[20]<<endl;
    cout<<"Inside WaysToGetSum main using Dynamic Programming "<<Ways[40]<<endl;
    // Stopping the timer
    high_resolution_clock::time_point t4 = high_resolution_clock::now();

    // Calculating execution time in both the approaches
    auto recDuration = duration_cast<microseconds>( t2 - t1 ).count();
    auto dpDuration = duration_cast<microseconds>( t4 - t3 ).count();

    cout<<"Calculation of Four Sums took "<<recDuration<<" microseconds using recursion"<<endl;
    cout<<"Calculation of Four Sums took "<<dpDuration<<" microseconds using DP"<<endl;

    return 0;
}

Let’s take a pause and take a guess about How much faster DP approach would be compared to recursion ?

Ready for the results ?

Here it is

Inside WaysToGetSum main using recursion 4
Inside WaysToGetSum main using recursion 64
Inside WaysToGetSum main using recursion 7921
Inside WaysToGetSum main using recursion 119814916
Inside WaysToGetSum main using Dynamic Programming 4
Inside WaysToGetSum main using Dynamic Programming 64
Inside WaysToGetSum main using Dynamic Programming 7921
Inside WaysToGetSum main using Dynamic Programming 119814916
Calculation of Four Sums took 946019 microseconds using recursion
Calculation of Four Sums took 18 microseconds using DP