How to find all combinations that can form n?

Question

Mathematics

Good evening! In general, there is some set [100, 50, 25, 10, 5, 1] ​​and n. I need to find all combinations that can form n. For example, for n = 100 and the set above, the answer is 194 combinations. Since I have trouble with algorithms, I don’t even know how to formulate it correctly in order to google it.

Answer 1

#include <iostream>
#include <vector>

std::vector<int> arr = { 100, 50, 25, 10, 5, 1 };
int n = 100;
int matches = 0;

void calc( int val, unsigned int offs ) {
  if( val == n ) {
    matches++;
    return;
  } else if( val > n ) {
    return;
  }
  for( unsigned int i = offs; i < arr.size(); ++i ) {
    calc( val + arr[i], i );
  }
}

int main( int argc, char** argv ) {
  calc( 0, 0 );
  std::cout << matches << std::endl;
  return( EXIT_SUCCESS );
}

Answer 2

Maybe something like this: https://prog-cpp.ru/combinations/?