Subset sum to target

#1

i am getting time limit exceeded in two of the test cases through this approach. can you tell me what is the mistake in my code??
here it is

#2

Hi, please note that n <= 10^3 and sum <= 1e5, therefore, you can’t make an array of size n x sum.

Try to optimize the space complexity.

#3

i am not able to optimise it please help

#4

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.