494. Target Sum

2-D DP

/*
 * @lc app=leetcode id=494 lang=cpp
 *
 * [494] Target Sum
 *
 * https://leetcode.com/problems/target-sum/description/
 *
 * algorithms
 * Medium (47.77%)
 * Likes:    11630
 * Dislikes: 387
 * Total Accepted:    813.1K
 * Total Submissions: 1.6M
 * Testcase Example:  '[1,1,1,1,1]\n3'
 *
 * You are given an integer array nums and an integer target.
 *
 * You want to build an expression out of nums by adding one of the symbols '+'
 * and '-' before each integer in nums and then concatenate all the
 * integers.
 *
 *
 * For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1
 * and concatenate them to build the expression "+2-1".
 *
 *
 * Return the number of different expressions that you can build, which
 * evaluates to target.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,1,1,1,1], target = 3
 * Output: 5
 * Explanation: There are 5 ways to assign symbols to make the sum of nums be
 * target 3.
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1], target = 1
 * Output: 1
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 20
 * 0 <= nums[i] <= 1000
 * 0 <= sum(nums[i]) <= 1000
 * -1000 <= target <= 1000
 *
 *
 */

// @lc code=start
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];
    }
};
// @lc code=end

• 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> t;
            for (auto a : dp)
            {
                int sum = a.first, count = a.second;
                t[sum + num] += count;
                t[sum - num] += count;
            }
            dp = t;
        }
        return dp[target];
    }
};

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