494. Target Sum

Medium

Description

給定一個整數陣列 nums 和一個目標值 target，對每個數字添加 + 或 - 號，求使得運算結果等於 target 的方法數。

Example:

Input: nums = [1,1,1,1,1], target = 3 Output: 5

Intuition#

將問題轉化為子集和：找出一個子集 P 使得 sum(P) = (sum + target) / 2。

設加正號的子集和為 P，加負號的子集和為 N
P + N = sum，P - N = target
所以 P = (sum + target) / 2
問題轉化為：從 nums 中選出若干數字使得和為 (sum + target) / 2 的方案數
若 (sum + target) 為奇數或 target > sum，答案為 0

Approaches#

1: 回溯（暴力）#

概念: 對每個數字嘗試 +/-，遞迴搜尋所有可能。
時間複雜度: O(2^n)
空間複雜度: O(n) 遞迴深度

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        return backtrack(nums, target, 0, 0)
    }

    private fun backtrack(nums: IntArray, target: Int, index: Int, currentSum: Int): Int {
        if (index == nums.size) {
            return if (currentSum == target) 1 else 0
        }
        return backtrack(nums, target, index + 1, currentSum + nums[index]) +
               backtrack(nums, target, index + 1, currentSum - nums[index])
    }
}

⭐2: 0/1 背包 DP#

概念: 轉化為子集和問題後，用 0/1 背包求方案數。dp[j] 代表和為 j 的方案數。
時間複雜度: O(n * target)，target 為 (sum + target) / 2
空間複雜度: O(target)

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        val sum = nums.sum()
        if ((sum + target) % 2 != 0 || sum < Math.abs(target)) return 0
        val subsetSum = (sum + target) / 2
        val dp = IntArray(subsetSum + 1)
        dp[0] = 1
        for (num in nums) {
            for (j in subsetSum downTo num) {
                dp[j] += dp[j - num]
            }
        }
        return dp[subsetSum]
    }
}

🔑 Takeaways#

Pattern: 問題轉化 — 將 +/- 選擇問題轉化為 0/1 背包子集和問題
關鍵技巧: 遇到「每個元素二選一」的計數問題，嘗試用數學推導轉化為背包問題；0/1 背包內層要逆向遍歷