How to solve a problem with enumeration?

Question

Programming

The task is as follows:
"There is a certain fixed number of coins with denominations of 2,3,5. It is necessary to create an algorithm of actions that is guaranteed to check the possibility of obtaining a given number by summing the available coins."
I thought to solve it through a dynamic array and recursion, but so far I'm not good at it. Maybe there is another better solution

Answer 1

The easiest solution to understand is a complete search. Stupidly 3 cycles - how many coins with a face value of 2 were taken, how many coins with a face value of 3 and how many coins with a face value of 5. Each cycle from 0 to <How much to collect> / face value. Then we check that the sum has converged. Moreover, you can skip the last cycle and just check that the rest can be scored with nickels.

bool CanExchange(int n, int have2, int have3, int have5) {
  for(int take2 = 0; take2 <= min(have2, n/2); ++take2) {
    int left2 = n - 2*take2;
    for (int take3 = 0; take3 < min(have3, left2/3); ++take3) {
      int left23 = left2 - take3*3;
      if (left23 % 5 == 0 && left23 / 5 <= have5) {
        return true;
      }
    }
  }
  return false;
}

But this is for this specific task, where there are only 3 types of coins. In general, you need to write a recursive function instead of nested loops, which will take how much is left to collect and what type of coins to sort through.
The fastest solution is dynamic programming.
F(n,k) - is it possible to get the number n with the first k types of coins.
F(0.0) = 1
F(*, 0) = 0 F(n,k) = Sum(i = 0..have
[k]) F(ni*value[k], k-1)
the same recursive enumeration, only with memoization. You can rewrite this in two loops and optimize for memory to O(n).