🔗 🟡 494. Target Sum

tags: `陣列(Array)` `動態規劃(DP)` `回溯(Backtracking)`

題意

給定一個非負的整數陣列 $nums$ 和一個整數 $target$ 。

你想要利用 $nums$ 中的數字來建立一個表達式，方式是在每個數字前面加上符號 $+$ 或 $-$ ，然後把所有數字連接起來。

例如，如果 $nums = [2, 1]$ ，你可以在 $2$ 前加 $+$ ，在 $1$ 前加 $-$ ，然後連接起來形成表達式 $+2-1$ 。

返回你可以建立的不同表達式數量，這些表達式的運算結果為 $target$ 。

約束條件

$1 \leq nums.length \leq 20$
$0 \leq nums[i] \leq 1000$
$0 \leq \sum(nums[i]) \leq 1000$
$-1000 \leq target \leq 1000$

思路

這題存在回溯(Backtracking) 解法，但用 Python 提交會超時，需要使用其他語言提交。

令所有元素的和為 $s$ ，添加符號 $+$ 的數字和為 $pos$ ，添加符號 $-$ 的數字和為 $neg$ ，則有：

$\begin{aligned} pos - neg &= \sum(nums) = s\\ pos + neg &= target \end{aligned}$

解聯立得 $pos = \frac{s + target}{2}$ ，但根據約束條件， $pos$ 必須為整數，且 $pos \geq 0$ ，若不滿足則直接返回 $0$ 。

故問題可以轉換成：在 $nums$ 中選取一些數字，使其和為 $pos$ 的方法數。如此便可以使用動態規劃(DP) 來解決。

方法一：記憶化搜尋(Memoization)

令 $dfs(i, j)$ 表示在前 $i$ 個數字中取若干個數字，能夠使和為 $j$ 的方法數。則有以下遞迴式：

$dfs(i, j) = dfs(i-1, j) + dfs(i-1, j-nums[i-1])$ $df s (i, j) = df s (i - 1, j) + df s (i - 1, j - n u m s [i - 1])$
- 若選第 $i$ 個數字 (下標為 $i-1$ )，需要在剩餘的前 $i-1$ 個數字中取若干個數字，使其和為 $j-nums[i-1]$
- 若不選第 $i$ 個數字，則需要在剩餘的前 $i-1$ 個數字中取若干個數字，使其和為 $j$
遞迴終點為 $i = 0$ ，若 $j = 0$ 代表合法情況，則返回 $1$ ；否則返回 $0$ 。
遞迴入口為 $dfs(n, pos)$ ，其中 $n$ 為陣列長度， $pos$ 為目標和，代表在前 $n$ 個數字中取若干個數字，使其和為 $pos$ 的方法數。
可以注意到，若 $j < nums[i-1]$ ，則無法選擇第 $i$ 個數字，則只需要考慮不選的情況即可，可以剪枝(Pruning) 。

由於存在大量重複計算，因此可以使用 @cache 裝飾器（Python）或者 memo 陣列（C++）來進行記憶化(Memoization) 。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot \text{pos})$ $O (n \cdot pos)$ ，其中 $n$ $n$ 為陣列長度， $\text{pos}$ $pos$ 為目標和。
- 總共有 $n \cdot \text{pos}$ 個狀態，每個狀態需要 $\mathcal{O}(1)$ 的時間進行計算。
空間複雜度： $\mathcal{O}(n \cdot \text{pos})$ ，和狀態數量相同。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        pos = target + sum(nums)
        if pos % 2 or pos < 0:
            return 0
        pos //= 2
        @cache
        def dfs(i: int, j: int) -> int:
            if i == 0:
                return 1 if j == 0 else 0
            if j < nums[i - 1]: # Pruining
                return dfs(i - 1, j)
            return dfs(i - 1, j) + dfs(i - 1, j - nums[i - 1])
        return dfs(n, pos)

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        target += accumulate(nums.begin(), nums.end(), 0);
        if (target % 2 || target < 0) return 0;
        target /= 2;
        vector<vector<int>> memo(n + 1, vector<int>(target + 1, -1));
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i == 0) return j == 0;
            if (memo[i][j] != -1) return memo[i][j];
            if (j < nums[i - 1]) return dfs(i - 1, j); // Pruning
            return memo[i][j] = dfs(i - 1, j) + dfs(i - 1, j - nums[i - 1]);
        };
        return dfs(n, target);
    }
};

方法二：使用滾動陣列(Scorelling Array)優化空間

注意到在方法一中，狀態的轉移都只和 $i-1$ 的狀態有關，因此可以使用滾動陣列(Scorelling Array) 的方式進行空間優化。

以同樣的方式計算出 $pos$ ，然後定義一個陣列 $dp$ ，其中 $dp[j]$ 表示在前 $i$ 個數字中取若干個數字，使其和為 $j$ 的方法數。由於我們只要考慮 $i-1$ 的狀態，因此只需要保存一個長度為 $pos$ 的陣列即可。

初始化 $dp[0] = 1$ ，表示不選取任何數字，結果為 $0$ 的表達式有 $1$ 種方法。
遍歷 $nums$ $n u m s$ 中的每個數字 $x$ $x$ ，對於每個 $j \in [x, pos]$ $j \in [x, p os]$ ，更新 $dp[j] += dp[j - x]$ $d p [j] + = d p [j - x]$ 。
- 這裡的 $dp[j - x]$ 表示在前 $i-1$ 個數字中取若干個數字，使其和為 $j-x$ 的方法數，因此可以選擇加上 $x$ 來形成和為 $j$ 的情況。
- 為了避免計算時使用到已經被修改的值，我們需要由大到小遍歷 $j$ 。
最後答案為 $dp[pos]$ ，即前 $n$ 個數字中組成和為 $pos$ 的方法數。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot \text{pos})$ $O (n \cdot pos)$ ，其中 $n$ $n$ 為陣列長度， $\text{pos}$ $pos$ 為目標和。
- 總共有 $n \cdot \text{pos}$ 個狀態，每個狀態需要 $\mathcal{O}(1)$ 的時間進行計算。
空間複雜度： $\mathcal{O}(\text{pos})$ ，只保存一維的狀態陣列 $dp$ 。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        pos = target + sum(nums)
        if pos % 2 or pos < 0:
            return 0
        k = pos // 2
        dp = [0] * (k + 1)
        dp[0] = 1
        for x in nums:
            for j in range(k, x - 1, -1):
                dp[j] += dp[j - x]
        return dp[k]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        target += accumulate(nums.begin(), nums.end(), 0);
        if (target % 2 || target < 0) return 0;
        target /= 2;
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = target; j >= nums[i]; j--)
                dp[j] += dp[j - nums[i]];
        return dp[target];
    }
};