494. Target Sum

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

2 維 DP

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        // row 是個數，後續的空間優化可以拿掉他，因為我們不需要知道個數
        // map 的 key 是總和，val 是計數 count
        vector<unordered_map<int, int>> dp(n + 1);
        
        // 起始值是 1
        dp[0][0] = 1;
        
        // i 指的是 nums 的 index
        for(int i = 0; i < n; ++i) {
            // 將結果存到 dp 表格中
            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];        
    }
};

• 時間複雜度：
  $O(T\cdot N)$
• 空間複雜度：
  $O(T\cdot N)$

DP 空間改進

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        // 初始值是 1
        dp[0] = 1;
        for (int num : nums) {
            unordered_map<int, int> t;
            for (auto a : dp) {
                // key 存 sum 的總和
                int sum = a.first, count = a.second;
                // 對於每個數字我們可以選擇將其加上或減去
                // 加法的情況
                t[sum + num] += count;
                // 減法的情況
                t[sum - num] += count;
            }
            dp = t;
        }
        return dp[target];
    }
};

• 時間複雜度：
  $O(T\cdot N)$
• 空間複雜度：
  $O(T)$