This is the code for finding whehther there exists a subset equal to the given sum or not?
The interesting part is that when i change the oreder of rec() in return dp[idx][left_sum] = rec(v,idx+1,n, left_sum) | rec(v, idx+1, n, left_sum — v[idx]); i get different result.
Thanks for looking into it in advance.❤️
here is the test case i have attached
100 5142
57 68 27 100 69 49 100 51 71 63 77 20 63 4 11 31 21 23 94 5 56 54 15 88 61 89 5 22 83 55 90 39 74 16 38 42 17 37 93 39 52 69 59 14 24 21 96 96 43 89 100 51 95 15 38 7 55 42 28 37 49 69 75 74 36 12 16 52 1 60 43 52 80 53 65 55 73 12 50 68 100 50 18 94 16 7 100 70 1 79 58 49 47 32 74 35 95 89 38 47
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#include "./lib/debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define F(type, i, s, n, step) for (type i = s; (step) > 0 ? i < (n) : i > (n); i += (step))
#define FN(type, i, s, n, step) for (type i = s; (step) > 0 ? i <= (n) : i >= (n); i += (step))
#define pb push_back
// #define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<char, int> pci;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const ll MAXM = 1e5;
int dirx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
int diry[8] = {0, 1, -1, 0, -1, 1, -1, 1};
int mod = 1e9 + 7;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double EPS = 1e-9;
double PI = acos(-1);
vl factors[MAXM + 5];
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void init()
{
for (ll i = 1; i <= MAXM; i++)
{
for (ll j = i; j <= MAXM; j += i)
{
factors[j].pb(i);
}
}
}
int bin_pow(int base, int pow)
{
int ans = 1;
while (pow)
{
if (pow & 1)
{
ans = 1LL * ans * base % mod;
}
base = 1LL * base * base % mod;
pow /= 2;
}
return ans;
}
int dp[105][1005];
int rec(vector<int> &v, int idx, int left_sum)
{
int n = v.size();
if (left_sum < 0)
return 0;
if (idx == n)
{
if (left_sum == 0)
return 1;
else
return 0;
}
if (left_sum == 0)
{
return 1;
}
if (dp[idx][left_sum] != -1)
{
return dp[idx][left_sum];
}
return dp[idx][left_sum] = rec(v, idx + 1,left_sum) | rec(v, idx + 1, left_sum - v[idx]);
}
void solve()
{
int n, sum;
cin >> n >> sum;
vi v(n);
for (auto &e : v)
cin >> e;
int ans = rec(v, 0, sum);
cout << ans;
}
signed main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
std::cout.tie(NULL);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++)
{
#ifdef LOCAL
std::cerr
<< "Case # " << i << endl;
std::cout
<< "Case #" << i << endl;
#endif
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
~~~~~