Given an array of denominations and a value MAX, find the minimum set of coins that is possible to evaluate any value 'n' such that 1 <= n <= MAX

Clarifications:

1. the availability of each denomination can be assumed to be infinite.
2. the given array can be assumed to be sorted.
3. a valid set satisfying the needed criteria always exists

Example:

input: {1, 3, 5, 11}, MAX = 5
output: {1, 1, 3,}

explanation: the resultant set {1,1,3} is the set of minimum size that can give a sum of all values for n where 1 <= n <= 5 (since MAX=5 here) like below:

for 1 => {1}
for 2 => {1,1}
for 3 => {3}
for 4 => {1,3}
for 5 => {1,1,3}

The time complexity of my solution would be O(MlogN + NlogN) where M is the MAX value and N is the number of denominations.

SC: O(N)

#include<bits/stdc++.h>
using namespace std;


int getSize(set<int> &coinsSet, int M, int target){
  if(target > M)
    return 0;

  //O(logN)
  auto itr = coinsSet.upper_bound(target);
  itr--;
  int nextCoin = *itr;

  return 1 + getSize(coinsSet, M, target + nextCoin);
}
int main(){
  int n;
  cin>>n;
  vector<int> coins(n);
  for(int i = 0; i < n; i++)
    cin>>coins[i];
  

  set<int> coinsSet;

  //total TC of for loop : O(NlogN)
  for(int val : coins)
    coinsSet.insert(val);
  int M;
  cin>>M
  int result = getSize(coinsSet, M, 1);
  cout<<"ANSWER IS: "<<result<<"\n";
  return 0;
}

Not sure if a more optimal solution exists. Please post it in comments if anyone has more optimal solution or a different approach.