494. Target Sum

📝 Problem Details

• Title: 494. Target Sum
• Link: https://leetcode.com/problems/target-sum/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

input integer array nums input integer target build an expression out of nums by adding one of the symbols + or - before each integer return the number of different expressions that you can build which evaluates to target

Note: This problem can be solved with a more efficient bottom-up approach but for the purpose of comprehension I’ve opted for a top-down solution as it’s more intuitive and results in AC

💭What Were My Initial Thoughts?

- enumaration question (backtracking) --> would be exponential
- can we optimize it with DP?

1. subproblem?
	- Given an index i and a running sum, determine the number of ways to assign
	   + or - to the remaining elements in nums[i:] such that the final sum equals 
	     target.

2. top-down or bottom-up?
	- since the problem is initially seens as a backtracking problem
	- this would involve a DFS recursive approach
	- we can implement memoization to the original method which would indicate a top-down approach

3. dp state
	- dp[i][sum] represents the number of ways to reach sum using elements from index i onwards
	- base case: if i == nums.size(), return 1 if sum ==  target
	- return 0 otherwise
	- use an unordered map for O(1) lookup in memoization table

4. state transition
	- dp[i][sum] = dp[i+1][sum + nums[i]] + dp[i+1][sum - nums[i]]

💡 Explanation of Solution

- Instead of recomputing results for the same `(i, sum)`, we use memoization to store results.

⌛ Complexity Analysis

Time Complexity: O(n * m)
- where N is the number of elements in nums
- and M is the sum of all elements in nums

Space Complexity: O(n * m)

Top-down optimizes the original recursive backtracking from O(2^n)

💻 Implementation of Solution

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<string, int> memo; // memo table to store already computed results
        return dfs(nums, 0, 0, target, memo);
    }
 
    int dfs(vector<int>& nums, int i, int sum, int target, unordered_map<string, int>& memo) {
        // base case: if we have processed all numbers
        if(i == nums.size()) {
            return sum == target ? 1 : 0; // return 1 if the sum matches target
        }
 
        // create unique key to store results for the current (index, sum) pair
        string key = to_string(i) + "," + to_string(sum);
 
        // if this state has already been computed, return the stored value
        if (memo.find(key) != memo.end()) return memo[key];
 
        // recursive case: add or substract the current number and explore both paths
        int add = dfs(nums, i + 1, sum + nums[i], target, memo);
        int subtract = dfs(nums, i + 1, sum - nums[i], target, memo);
 
        // store computed result in the memo table to avoid redundant calculations
        return memo[key] = add + subtract;
    }
};