Number of unique combination of numbers from an array whose sum equals to target (Recursion + Memoization)

Question

Dynamic programming question:

Consider a game where a player can score 3 or 5 or 10 points in a move.

Given a total score n, find the number of distinct combinations to reach the given score.

I am trying to solve it using recursion + memorization.

My recursion-only approach:

long long int countrecur(long long int n, long long int min)
{   
    if (n==0)
        return 1;     
    
    else if(n<0)
        return 0;
    
    else 
    {
        long long int ans=0;

        if(min<=3)
            ans+=countrecur(n-3,3);

        if(min<=5)
            ans+=countrecur(n-5,5);

        if(min<=10)
            ans+=countrecur(n-10,10);
        
        return ans;
    }

}

long long int count(long long int n)
{
   return countrecur(n,0);
}

It seems to be working but I am not able to find how to memorize the results of subproblems.

Recursion+Memorization attempt:

#include<iostream>
#include<vector>
using namespace std;

long long int countrecur(long long int n, long long int min, vector<long long int> &dp)
{
    if (n < 3 && n!=0)
        return 0;
    
    if (n == 0||dp[n]!=0)
        return dp[n];

    else
    {
        long long int ans = 0;
        if (min <= 3)
            ans += countrecur(n - 3, 3,dp);
        
        if (min <= 5)
            ans += countrecur(n - 5, 5,dp);
        
        if (min <= 10)
            ans += countrecur(n - 10, 10,dp);

        dp[n] = ans;

        return ans;
    }

}

long long int count(long long int n, vector<long long int>& dp)
{
    return countrecur(n, 0,dp);
}

int main()
{
    int n;
    cin >> n;
    vector<long long int>dp(n+1, 0);
    dp[0] = 1;
    cout << count(n,dp) << endl;
}

It seems to be failing for inputs like n=20 where some branches become equal at the root of the recursion tree.

20=15+5; 20={10,5}+{5}={10,5,5}

20=10+10; 20={5,5}+{10}={5,5,10}

Answer 1

Suppose you want a way for a score of 8,

So there is only one way to make a change,i.e.:

{3,5}

But, The code above returns 2 for it, Because:

That is considering (3,5) and (5,3) differently.

---

So, What to do?

Recursion should follow either the given ongoing value or not at all use it again.

That means the order of use of values should be maintained.

---

Pseudocode:

Array = [3,5,10]
index = 0 
value = 20

ways = Recursion(Array,index,value)

---

Recursion:

function Recursion(Array,index,value)

    if(value == 0)
        return 1

    if(value < 0)
        return 0

    if(index == 3)
        return 0

    return Recursion(Array,index,value - Array[index]) + Recursion(Array,index+1,value)

---

Memoization:

To memorize the solution, We need to use two parameters i.e. value and index.

---

Why the code in the question is not returning correct output?

Because for each index, we will have different ways to achieve the same value.

Let's take an example:

value = 15
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] // dp array

Ways for the min == '3' is one:

dp = [1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1]

While going through min == '5':

dp = [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]

But when recursion goes for min == '10' and n == 5:

1 is returned but there is no way for the score of 10 to make a total of 5.

That's why The above-memorized code will return 4 for 15 but the correct output should be 3.