memoization in C++

Question

Given a score by team in cricket, find/print all configs/ways to get to the score. There are 3 ways to score 2, 3 and 7

Example: Score: 10

Output: (0,1,1) (0,2,2) (0,0,5)

void out(int score, int two, int three, int seven)
{
    if(score == 0)
    {
        cout << "(" << two << ", " << three << ", " << seven <<  ")" << endl;
    }
    else if (score < 0)
    {
        return;
    }
    else
    {
        outputs(score - 7, two, three, seven + 1);
        outputs(score - 3, two, three + 1, seven);
        outputs(score - 2, two + 1, three, seven);        
    }
    return;
}

I do get the correct answers, but with repeats and also wanted to use memoization which i am really confused how to implement (0, 1, 1) (0, 1, 1) (2, 2, 0) (2, 2, 0) (2, 2, 0) (2, 2, 0) (2, 2, 0) (2, 2, 0) (5, 0, 0)

Answer 1

To avoid repetition you need to impose an ordering, for example not allowing using score 7 if you previously used a score 3.

void out(int score, int two, int three, int seven, int maxscore)
{
    ...
    else {
        if (maxscore >= 7) output(score-7, two, three, seven+1, 7);
        if (maxscore >= 3) output(score-3, two, three+1, seven, 3);
        if (maxscore >= 2) output(score-2, two+1, three, seven, 2);
    }
}

Using memoization instead would be more complex (and even probably not so useful) in this problem because you're looking for enumerating all solutions (not just counting them).

The idea of memoization is to keep a table to avoid recomputing the same subproblem. In this case the subproblem is defined by the score and the maximum score you're allowed to use, however the solution needs to take into account also how many two three and seven you already used and if you also add them to the key then each key will be only visited once (so no point in trying to memoize it).

Things are different if you only need to count in how many different ways you can reach the score because in that case the solution to the subproblem is just a number and you can use it to solve the original problem.