給定一個只含正整數的非空陣列
nums，判斷能否將其分割為兩個子集，使得兩個子集的元素總和相等。
Example:
Input: nums = [1,5,11,5] Output: true
Intuition
TIP
問題等價於：能否從陣列中選出若干元素，使其總和恰好等於全部總和的一半？
- 如果總和是奇數，直接回傳 false
- 轉化為 0/1 背包問題：目標容量 =
sum / 2 dp[j]表示是否能用部分元素湊出和為j
Approaches
1. 2D DP (Standard 0/1 Knapsack) — O(n * target) / O(n * target)
- Idea:
dp[i][j]表示前i個元素能否湊出和j - Time:
O(n * target) - Space:
O(n * target)
class Solution {
fun canPartition(nums: IntArray): Boolean {
val sum = nums.sum()
if (sum % 2 != 0) return false
val target = sum / 2
val n = nums.size
val dp = Array(n + 1) { BooleanArray(target + 1) }
for (i in 0..n) dp[i][0] = true
for (i in 1..n) {
for (j in 1..target) {
dp[i][j] = dp[i - 1][j]
if (j >= nums[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]]
}
}
}
return dp[n][target]
}
}⭐ 2. 1D DP (Space Optimized 0/1 Knapsack) — O(n * target) / O(target)
- Idea: 壓縮到一維，從後往前遍歷避免重複選取同一元素
- Time:
O(n * target) - Space:
O(target)
class Solution {
fun canPartition(nums: IntArray): Boolean {
val sum = nums.sum()
if (sum % 2 != 0) return false
val target = sum / 2
val dp = BooleanArray(target + 1)
dp[0] = true
for (num in nums) {
for (j in target downTo num) {
dp[j] = dp[j] || dp[j - num]
}
}
return dp[target]
}
}🔑 Takeaways
- Pattern: 0/1 背包 — 每個元素只能用一次，判斷能否達到目標值
- Key trick: 一維 DP 必須從後往前遍歷（
downTo），確保每個元素只被選一次；如果從前往後會變成完全背包