How to determine all ways to pay the amount n using coins of denominations of 1, 5, 10, 15, 20, 50 kopecks?

Question

C++ / C#

Hello!
Please tell me how to determine all the ways to pay the amount n using coins of denominations of 1, 5, 10, 15, 20, 50 kopecks, n is entered from the keyboard, and the numbers 1, 5, 10, 15, 20, 50 are stored in the array. I did the algorithm, but it did not work quite correctly, it gave out only ways with the same numbers.
Thanks in advance!)

Answer 1

#include <iostream>
#include <string>

using namespace std;
 
int cs[] = {1, 2, 5, 10, 50, 100, 200, 500, 1000, 2000, 5000}, s;
 
void f(int sq, int i, string v) {
    if (sq == 0) cout << v << "\n"; 
    else if (sq > 0 && i >= 0) {
        f(sq - cs[i], i, v + (v == "" ? " " : "+") + to_string(cs[i])); 
        f(sq, i - 1, v);
    }
}
 
int main() { 
  cin >> s;
  f(s, sizeof(cs)/sizeof(cs[0]) - 1, "");
  return 0;
}

Answer 2

This is the knapsack problem .
Solution via dynamic programming:

int Count(vector<int> coins, int n) {
  vector<int> cnt(n+1, 0);
  cnt[0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int coin : coins) {
      if (i+coin <= n) cnt[i+coin] += cnt[i];
    }
  }
  return cnt[n];
}