target-sum

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];
    }
};

T: $O(T \cdot N)$
S: $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];
    }
};

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

494. Target Sum​

494. Target Sum