給定一個整數陣列
nums和一個目標值target，對每個數字添加+或-號，求使得運算結果等於target的方法數。
Example:
Input: nums = [1,1,1,1,1], target = 3 Output: 5
Intuition
TIP
將問題轉化為子集和：找出一個子集 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. Backtracking (brute force) — O(2^n) / O(n)
- Idea: 對每個數字嘗試 +/-，遞迴搜尋所有可能。
- Time:
O(2^n) - Space:
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 Knapsack DP — O(n * target) / O(target)
- Idea: 轉化為子集和問題後，用 0/1 背包求方案數。
dp[j]代表和為 j 的方案數。 - Time:
O(n * target)，target 為(sum + target) / 2 - Space:
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 背包子集和問題
- Key trick: 遇到「每個元素二選一」的計數問題，嘗試用數學推導轉化為背包問題；0/1 背包內層要逆向遍歷