Target Subset sum to k

#1

https://ide.codingblocks.com/s/411577

here please check my code, it runs fine on my machine

#2

For this question, the constraints given are very strict.
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.