Time Complexity: O(N*T), there are total of N*T states.
Space Complexity: O(N*T), additonal space used to for memo table.

Space Optimization Approach

Algorithm

If we closely look the relation,

dp[ind][target] = dp[ind-1][target] + dp[ind-1][target-arr[ind]]

We see that to calculate a value of a cell of the dp array, we need only the previous row values. So, we don’t need to store an entire array. Hence we can space optimize it.

Note: We first need to initialize the first row as we had done in the tabulation approach.

Code

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051