c++ - Dynamic programming doesn't retrieve all the values that I expect

Question

Here's the problem that I'm trying to solve:

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1}, {1,1,2}, {2,2}, {1,3}.

So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Here's my solution:

#include <iostream>
#include <vector>
#include <optional>

std::optional<std::vector<int>> findCoins(int n, int array[], int nrCoins)
{
    if (n == 0) return std::vector<int>();
    if (n < 0) return std::nullopt;

    for (int i = 0; i < nrCoins; i++)
    {
        int x = n - array[i];
        std::optional<std::vector<int>> xRes = findCoins(x, array, nrCoins);
        if (xRes != std::nullopt)
        {
            xRes->push_back(array[i]);
            return xRes;
        }
    }
    return std::nullopt;
}

int main()
{
    int vector[3]{ 1, 2, 3 };
    int nr = 0;
    std::vector<int> coinuri = findCoins(4, vector, 3).value();
    for (int num : coinuri)
    {
        std::cout << num << " ";
    }
    return 0;
}

For that example, the recursion tree looks like this:

^{it's not the best picture}

But, instead of getting 7 results from my program (because in the tree there are 7 leafs with value = 0), I only get 1 result, and that one is the most left-sided one.

I think that in order to get 7 results instead of 1, I should use a matrix and store each result - that's why my program only returns 1. But, how can I do that using std::vector?

question from:https://stackoverflow.com/questions/65906994/dynamic-programming-doesnt-retrieve-all-the-values-that-i-expect

Answer 1

Waitting for answers