Subset Sum Problem Solution With Memoization
Subset sum problem solved using memoization. TC: O(n*m), SC: O(n*m) for dp array and O(n+m) stack space.
Problem
class Solution {
public int findTargetSumWays(int[] nums, int target) {
/*
it is similar to subset sum equal to target
given (+1 + 1 + 1 + 1) - (1) = 3
i.e. s1-s2 = k ( s1 and s2 are the subsets)
we know s1+s2 = sum
i.e k+s2+s2 = sum => s2 = (sum-k)/2
edge cases : sum-k>=0 because, 0<=nums[i]<=1000 given So,sum can't be less than 0
also (sum-k)/2 can not be fraction, as s2 can't be equal to a fraction value as the array is integer.
*/
int sum =0;
for(int i : nums){
sum+=i;...