494. Target Sum

2-D DP

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        int n = nums.size();
        vector<unordered_map<int, int>> dp(n + 1);

        dp[0][0] = 1;

        for(int i = 0; i < n; ++i)
        {

            for(auto a : dp[i])
            {
                int sum = a.first, count = a.second;
                dp[i + 1][sum + nums[i]] += count;
                dp[i + 1][sum - nums[i]] += count;
            }
        }
        return dp[n][target];
    }
};

• T: $O(T \cdot N)$
• S: $O(T \cdot N)$

Space improved

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        dp[0] = 1;

        for (int num : nums) {
            unordered_map<int, int> next_dp;
            for (const auto& [s, cnt] : dp) {
                next_dp[s + num] += cnt;
                next_dp[s - num] += cnt;
            }
            dp = move(next_dp);
        }
        return dp[target];
    }
};

• T: $O(T \cdot N)$
• S: $O(T)$