Https://ide.codingblocks.com/s/342142

#1

2 test cases not passing, please point out the error

#2

Hey @jayasmit98 can you tell me which test case numbers you are failing?

#3

0 and 1 , shows run error

#4

Okay, @jayasmit98 I’ll debug your code nd let you know.

#5

hey @jayasmit98 you are getting run time error because you are making dp array in ispossible function again and again. make a global dp array of required size and use it. Run time error is coming cause of very big value of n. Try this & if it still not works. Do let me know :smile:

#6

how am I declaring dp array again and again considering ispossilble function is not recursive?

#7

Hey @jayasmit98 the idea is to do this question in O(n) as per the given constraint. You are initializing a 2-d array. There are two ways to optimize it.

  1. note that you only need the previous state dp[i - 1] to determine the answer for the current state. So one way is to just maintain 2 states and keep on updating the previous state after calculating the current state answers. (see https://www.geeksforgeeks.org/subset-sum-problem-osum-space/ for implementation details)
  2. change your dp slightly as in https://stackoverflow.com/questions/51151923/space-optimization-of-dp-solution-of-subset-sum.
    This might help you :smile:
#8

Moreover if you still finds any issue , you can ask me . I will be happy to help :grinning: