LeetCode 筆記 - 494. Target Sum

Posted on

題目在此 494. Target Sum

給定一個整數陣列 nums 與一個目標值 target。
請找出有多少種方法可以對 nums 中的每個元素加上正號或負號，使得最終的總和等於 target。

例如：

1
2
3
4
5
6
7
8
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

解題思維

這題我們可以使用動態規劃（Dynamic Programming）來解決。
關鍵在於我們需要考慮每個數字可以有兩種選擇：

  • 加上正號
  • 加上負號

我們定義一個 dp 陣列，其中 dp[i] 是一個字典（或 Counter），用來記錄使用前 i 個數字可以達成的所有可能總和及其對應的方法數量。
具體來說，對於每個數字 nums[i]，我們可以從前一個狀態 dp[i - 1] 中的每一個產生出的總和 k 出發，計算出兩個新的總和：k + nums[i] 和 k - nums[i]，並將這兩個總和的方法數量累加到 dp[i] 中。

Time complexity 是 $O(n * sum(nums))$
其中 n 是陣列的長度，sum(nums) 是陣列中所有數字的總和。這是因為我們每次都是在 $sum(nums)$ 的範圍中搜尋答案，而我們需要對每個數字都進行這樣的操作 (n 次)。

Space complexity 是 $O(sum(nums))$，因為我們需要存儲所有可能的總和及其對應的方法數量。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        # step 0: use Dynamic Programming algorithm
        # step 1: dp[i] keeps the (value, ways)
        #         k: every previous dp key
        #         v: every previous dp value (ways)
        #         dp[i][k - num[i]] += dp[i - 1][k]
        #         dp[i][k + num[i]] += dp[i - 1][k]
        # step 2: return dp[-1][target]

        # time complexity: O(n * sum(nums))
        # space complexity: O(sum(nums))

        size = len(nums)

        dp = [collections.Counter() for _ in range(size)]

        dp[0][nums[0]] += 1
        dp[0][-nums[0]] += 1

        for i in range(1, len(nums)):

            for k in dp[i - 1]:

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

        return dp[-1][target]

也許你也會想看看