we can optimise space comp to O(SUM) bt how do we reduce time comp in this case?
The Subset Sum To Target1
@archit_18 hey archit
We can solve the problem in Pseudo-polynomial time using Dynamic programming. We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0…j-1] with sum equal to i., otherwise false. Finally, we return subset[sum][n]
The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).
but the suggested method can go down your complexity to o(sum*n)
the constraints here are,
n can be 5000 and sum can go upto 10^7, so subset[sum][n] ?
@archit_18 In this worst case senario the code should go upto subset[10000000][500] it time complexity of this case O(5000*10000000)
yes ik the worst case time comp is (10^7 * 5000), but how it’s getting accepted?
and we cn’t use memory more than 10^8, right? so how do we declare dp array in worst case?
@archit_18 hey archit as I said earlier this problem is belong to np complete if you wants me to share some hint I can help in this case.
no need got AC. just got confused with given constraints. thanks
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.