-
Notifications
You must be signed in to change notification settings - Fork 1
/
subset sum problem.cpp
141 lines (112 loc) Β· 2.78 KB
/
subset sum problem.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
///////////////////////////////////////////
//Question/Info
subset sum problem
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
There is a subset (4, 5) with sum 9.
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.
///////////////////////////////////////////
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define setbits(x) __builtin_popcount(x)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ct(x) cout<<x<<endl;
#define ct2(x,y) cout<<x<<" "<<y<<endl;
#define forn(i,n) for(int i = 0; i < (int)(n); i++)
#define forx(i,x,n) for(int i = x; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define fsp(x,y) fixed<<setprecision(y)<<x;
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007 // (1e9+7)
#define pii pair<int,int>
#define pis pair<int,string>
#define vi vector<int>
#define vii vector<pii>
#define mii map<int,int>
//typedef long long int lli;
typedef long double ld;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
void c_p_c()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int subss(int arr[], int n, int W)
{
bool dp[n + 1][W + 1];
// for (int i = 0; i < n + 1; i++)
// dp[i][0] = true;
// for (int i = 0; i < W + 1; i++)
// dp[0][i] = false;
forx(i, 0, (n + 1)) {
forx(j, 0, (W + 1)) {
if (i == 0 or j == 0) {
dp[i][j] = false ;
if (j == 0) {
dp[i][j] = true;
}
}
else {
if (arr[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = ((dp[i - 1][j]) or (dp[i - 1][j - arr[i - 1]]));
}
}
}
}
return dp[n][W];
}
int32_t main() {
///////////
c_p_c();
///////////
// code
/*
int t ; cin >> t; while(t--){}
*/
int arr[] = {1, 2, 3, 4, 5, 7};
int W = 40 ;
int n = sizeof(arr) / sizeof(arr[0]);
if (subss(arr, n, W)) {
ct("Yes");
}
else {
ct("No");
}
// cerr << "time: " << clock() << " ms" << '\n';
return 0;
}
/*
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than sum,
// then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
//else, check if sum can be obtained by any
//of the following:
// (a) including the last element
// (b) excluding the last element
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
*/