Coin Change

#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define in insert
#define f first
#define sc second
#define M 1000005
#define MAX 10000000
#define inf 1000000
using namespace std;

int main()
{
  int n,tt;
  cin >> n >> tt;
  int coins[n];
  for(int i=1;i<=n;i++) cin >> coins[i];
  sort(coins,coins+(n+1));
  int k[n+2][tt+2];
  for(int i=0;i<=n;i++)
  {
    for(int w=0;w<=tt;w++)
    {
      if(i==0) k[i][w] = inf;
      else if(w==0) k[i][w] = 0;
      else if(coins[i]>w) k[i][w] = k[i-1][w];
      else k[i][w] = min(k[i-1][w],1+k[i][w-coins[i]]);
    }
  }

  int temp_tt = tt;
  for(int i=n;i>=1 && temp_tt;i--)
  {
    for(int w=temp_tt;w>=1 && temp_tt;w--)
    {
      if(k[i][w]==k[i-1][w]) continue;
      else
      {
        w = w-coins[i];
        temp_tt -= coins[i];
        cout << "coin = " << coins[i] << endl;
      }
    }
  }
  cout << k[n][tt] << endl;

  return 0;
}