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↵
5142↵
~~~~~↵
↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
~~~~~↵
↵
↵
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;↵
}↵
~~~~~↵
↵
~~~~~↵
↵
