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

dpmatrix, 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 0110100000. With adding number 3, it is same as shifting current mask for 3 places. It will be 0000110100. So, all possible values which we can make are same as bitwise

orof this masks: 0110100000 or 0000110100 = 0110110100. Complexity of this solution is .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

DPmatrix would be something likeDP[i][j]= max(DP[i- 1][j] ,DP[i- 1][j-A_{i}]).DP[i][j] — can we make sumjfrom firstielements. So, only current and previous conditions are important, just two arrays are enough. For iterating from biggest to lowest value we would have something likeDP[j] =max(DP[j],DP[j-A_{i}]). It is important to iterate from biggestjto the smallest — because we didn't calculateDP[j-A_{i}] for current position. In case we started from the lowest to the biggest, we would have first thatDP[j] =true, thanDP[j+A_{i}] =true, thanDP[j+ 2A_{i}] =trueand so on(and we have only one numberA_{i}).Second thing with bitset, probably you didn't understand well. Binary representation like 0110111000 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 $$$2^0, 2^1, \dots,.2^{16}$$$ 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

Can u check this, with some test cases, see if it workshope will pass, as max value of n is 1e5