494. Target Sum

Problem Statement

Pattern: Pattern DP Subset Partitioning

---

Solution

HashMap<Integer, Integer>[] cache;  
int find(int[] nums, int target, int n, int currSum) {  
   if (n < 0 && currSum == target) return 1;  
   if (n < 0) return 0;  
   
   // check entry in cache  
   HashMap<Integer, Integer> entry = cache[n];  
   if(entry != null && entry.containsKey(currSum)) 
	   return entry.get(currSum);
     
   int pos = find(nums, target, n - 1, currSum + nums[n]);  
   int neg = find(nums, target, n - 1, currSum - nums[n]);  
   
   // update entry in cache  
   if(entry == null) entry = new HashMap<>();  
   entry.put(currSum, pos+neg); cache[n] = entry;  
 
   return pos + neg;  
}  
  
public int findTargetSumWays(int[] nums, int target) {  
   cache = new HashMap[nums.length];  
   return find(nums, target, nums.length - 1, 0);  
}

TC : O(ns) SC : O(ns)

Brute Force :

int find(int[] nums, int target, int n, int currSum) {  
   if (n < 0 && currSum == target) return 1;  
   if (n < 0) return 0;  
   
   int pos = find(nums, target, n - 1, currSum + nums[n]);  
   int neg = find(nums, target, n - 1, currSum - nums[n]);  
   
   return pos + neg;  
}  
  
public int findTargetSumWays(int[] nums, int target) {  
   return find(nums, target, nums.length - 1, 0);  
}

TC : O(2^n)