#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");
}