DP

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

const int N = 10010;
int dp[N];

int func(int amount, vector<int> &coins)
{
    if (amount == 0)
        return 0;
    if (dp[amount] != -1)
        return dp[amount];
    int ans = INT_MAX;
    for (int coin : coins)
    {
        if (amount - coin >= 0)
        {
            ans = min(ans, func(amount - coin, coins) + 1);
        }
    }
    return dp[amount] = ans;
} 

int coinChange(vector<int> &coins, int amount)
{
    int ans = func(amount, coins);
    return ans == INT_MAX ? -1 : ans;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    vector<int> coins = {1, 2, 5};
    cout << coinChange(coins, 11);

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

const int N = 10010;
int dp[N][N];

int func(int ind, int amount, vector<int> &coins)
{
    if (amount == 0)
        return 1;
    if (ind < 0)
        return 0;
    if (dp[ind][amount] != -1)
        return dp[ind][amount];
    int way = 0;
    for (int coin_amount = 0; coin_amount <= amount; coin_amount += coins[ind])
    {
        way += func(ind - 1, amount - coin_amount, coins);
    }
    return dp[ind][amount] = way;
}

int coinChange(vector<int> &coins, int amount)
{
    memset(dp, -1, sizeof(dp));
    return func(coins.size() - 1, amount, coins);
}

int main()
{
    vector<int> coins = {1, 2, 5};
    cout << coinChange(coins, 5);

    return 0;
}
//////////////////////////
#include <bits/stdc++.h>
using namespace std;
int coin[1000], dp[1000][1000];
int coin_change(int n, int sum, int k)
{
    if (sum < 0)
        return 0;
    if (sum == 0 && k == 0)
        return 1;
    if (n == -1)
        return 0;
    if (dp[n][sum] != -1)
        return dp[n][sum];
    return dp[n][sum] = (coin_change(n - 1, sum - coin[n - 1], k - 1)) || (coin_change(n - 1, sum, k));
}
int main()
{
    int n, k, sum;
    cin >> n >> k >> sum;
    for (int i = 0; i < n; i++)
        cin >> coin[i];
    memset(dp, -1, sizeof(dp));
    coin_change(n, sum, k);
    cout << (dp[n][sum] ? "YES" : "NO");
}