Question: Given a set of "n" non-negative integers, and a value "sum", determine if there is a subset of the given set with sum equal to given sum.
Input Format: 1st Line: n sum 2nd Line: a1 a2……an (Array Values)
Constraints: 1<= n <= 5000 1<= sum <= 10^7 1<= Ai <=10^5
Output Format: Yes, if sum exist No, it sum does not exist
I wanted to use this https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ solution But creating an array dp[5000+1][10e7+1] is not possible. So what can be done?
You do not need first coordinate in dp matrix, current state can be calculated from previous state — two arrays for current and previous state, or calculating values from biggest to lowest with one array will be enough. About some optimization of speed, you can use bitset, only one bit is important for calculating each possible value (1 if we can make some value till now, otherwise 0).
For example you have maximum possible sum 10 and current mask
Unable to parse markup [type=CF_TEX]
. With adding number 3, it is same as shifting current mask for 3 places. It will beUnable to parse markup [type=CF_TEX]
. So, all possible values which we can make are same as bitwise or of this masks:Unable to parse markup [type=CF_TEX]
orUnable to parse markup [type=CF_TEX]
=Unable to parse markup [type=CF_TEX]
. Complexity of this solution isUnable to parse markup [type=CF_TEX]
.hey @allllekssssa thanks for replying!
Could you explain how reaching the current state from the previous state is possible when we calculate values from biggest to lowest?
Also the optimization you mentioned is quite cool but how does adding number 3 is same as shifting the mask by 3 places? (Is is related to 2^0 + 2^1 ,if it is, then wont this requires two places)
:)
Hi,
I will try to explain it a bit more.
Formula for calculating DP matrix would be something like
Unable to parse markup [type=CF_TEX]
,Unable to parse markup [type=CF_TEX]
). DP[i][j] — can we make sum j from first i elements. So, only current and previous conditions are important, just two arrays are enough. For iterating from biggest to lowest value we would have something like DP[j] =Unable to parse markup [type=CF_TEX]
. It is important to iterate from biggest j to the smallest — because we didn't calculateUnable to parse markup [type=CF_TEX]
for current position. In case we started from the lowest to the biggest, we would have first thatUnable to parse markup [type=CF_TEX]
, thanUnable to parse markup [type=CF_TEX]
, thanUnable to parse markup [type=CF_TEX]
and so on(and we have only one number Ai).Second thing with bitset, probably you didn't understand well. Binary representation like
Unable to parse markup [type=CF_TEX]
means, we can not make sum 1, we can make sum 2, we can make sum 3, we can not make sum 4, we can make sum 5 and so on (I hope you see pattern). So when you are adding new number, for example 3, it means: now you can make sum 3 for sure, you can make sum 5 for sure (because 2 was possible in previous step), we can make sum 6 ( 3 was possible in previous step), we can make sum 8 (five was possible in previous step). So if you have array of bits, and you have ones on places 2, 3, 5, now you will have ones on places 5,6,8 for sure ( it is shifting for 3 places right? ). After this observation you can do logical operation which I mentioned in the comment before.Just wanted to ask whether C++ map map<pair<int,int>,int> would work or not to reduce the unnecessary wastage of memory because not all the i,j pair will be used up for the solving the (n,sum) state ?
I think that you can not save on that way. In case you have array
Unable to parse markup [type=CF_MATHJAX]
after 17 steps you will be able to make all numbers smaller than $$$10^5$$$ and it is too much memory immediately.Can you please explain time complexity of this approach specially that divide by 32 part Thank you
can you please share the link of question so that i can submit my solution thanks
int n, k; cin >> n; vector<int> nums(n); for(int i = 0 ; i < n ; ++i) cin >> nums[i]; cin >> k; unordered_map<int, int> seen = {{0, 1}}; int count = 0, sum = 0; bool found = false; for (auto n: nums) { sum += n; count += seen[sum - k]; if (seen.end() != seen.find(sum - k)) { found = true; break; } seen[sum]++; } if(found) cout << "Yes" << '\n'; else cout << "No" << '\n';Can u check this, with some test cases, see if it works
hope will pass, as max value of n is 1e5