494. Target Sum

題目網址：https://leetcode.cn/problems/target-sum/

題意：給一 array nums 和整數 target, 在 nums 中每個整前添加 + 或 -, 然後串聯整個 nums 形成一個表達式：

e.g. nums = [2, 1] 可以在 2 前添加 +, 在 1 前添加 -, 形成表達式 +2-1

求運算結果等於 target 的不同表達式數目。

Solution 1：

想法：利用暴力法, 遞迴下去做（速度極慢）

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);

        if (target > abs(sum) || target < -abs(sum)) {
            return 0;
        }

        int res = 0;
        dfs(nums, 0, nums.size(), target, res);

        return res;
    }

    void dfs(const vector<int>& nums, const int i, const int n, const int target, int& res){
        if (i == n) {
            if (target == 0) {
                ++res;
            }
            return;
        }

        dfs(nums, i + 1, n, target + nums[i], res);
        dfs(nums, i + 1, n, target - nums[i], res);
    }
};

time：$O(2^n)$ ➔ nums 中每個數有兩種選擇
space：$O(n)$ ➔ 取決於遞迴的深度, 遞迴最大深度為 n

Solution 2：

想法：利用 DP, 可把這題看做是背包問題, 每一個 nums[i] 都有取正 or 取負兩種選擇

1. 定義狀態：

dp[i][j]：nums[1:i] 湊出 j 的方法數

2. 得到狀態轉移方程：

dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]

3. 初始化：

首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態

dp[0][0] = 1：代表沒有元素時, 湊出 0 的方案為 1 種

4. 注意事項：

本題 dp[i][j] 的 j 之範圍為 [-abs(sum), abs(sum)], 但 index 不允許負數, 因此統一加上 offset = abs(sum), 將其 mapping 到範圍 [0, 2 * abs(sum)]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);

        if (target > abs(sum) || target < -abs(sum)) {
            return 0;
        }

        nums.emplace(nums.begin(), 0); // nums 前面補 0

        // range：[-abs(sum), abs(sum)], 要 mapping 到 idx：[0, abs(sum)], 要加 offset
        vector<vector<int>> dp(n + 1, vector<int>(2 * abs(sum) + 1, 0));

        const int offset = abs(sum), n = nums.size();
        dp[0][0 + offset] = 1; // j = 0 被 mapping 到 0 + offset

        for (int i = 1; i <= n; ++i) {
            for (int j = -abs(sum); j <= abs(sum); ++j) {
                // 避免越界
                if (j - nums[i] >= -abs(sum) && j - nums[i] <= abs(sum)) {
                    dp[i][j + offset] += dp[i - 1][j - nums[i] + offset];
                }

                if (j + nums[i] >= -abs(sum) && j + nums[i] <= abs(sum)) {
                    dp[i][j + offset] += dp[i - 1][j + nums[i] + offset];
                }
            }
        }

        return dp[n][target + offset];
    }
};

time：$O(sum \cdot n)$ ➔ for loop, 其中 sum 為 nums 元素之和
space：$O(sum \cdot n)$ ➔ dp

Solution 3：

想法：Solution 2 的改進, 實際上 dp[i][j + offset] 只會用到上一列 dp[i - 1][X], 故不需要開到 $O(sum \cdot n)$ 的空間, 只需 $O(sum)$ 的空間即可

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);

        if (target > abs(sum) || target < -abs(sum)) {
            return 0;
        }

        nums.emplace(nums.begin(), 0); // nums 前面補 0

        // range：[-abs(sum), abs(sum)], 要 mapping 到 idx [0, abs(sum)], 要加 offset
        vector<int> dp(2 * abs(sum) + 1, 0);

        const int offset = abs(sum), n = nums.size();
        dp[0 + offset] = 1;

        for (int i = 1; i <= n; ++i) {
            vector<int> nextRow(2 * abs(sum) + 1, 0);

            for (int j = -abs(sum); j <= abs(sum); ++j) {
                if (j - nums[i] >= -abs(sum) && j - nums[i] <= abs(sum)) {
                    nextRow[j + offset] += dp[j - nums[i] + offset];
                }

                if (j + nums[i] >= -abs(sum) && j + nums[i] <= abs(sum)) {
                    nextRow[j + offset] += dp[j + nums[i] + offset];
                }
            }

            dp = move(nextRow);
        }

        return dp[target + offset];
    }
};

time：$O(sum \cdot n)$ ➔ for loop, 其中 sum 為 nums 元素之和
space：$O(sum)$ ➔ dp, nextRow 皆只需 $O(2 \cdot sum + 1)$