給定一個不重複的正整數陣列
nums和一個目標值target，求湊成target的排列數（不同順序算不同組合）。
Example:
Input: nums = [1,2,3], target = 4 Output: 7
Intuition
TIP
類似 Coin Change 但求排列數 — 外層迴圈遍歷目標值，內層遍歷 nums。
- 和 Coin Change 不同的是：不同順序算不同方案（排列而非組合）
dp[i]= 湊成金額i的排列數- 外層遍歷金額，內層遍歷 nums，這樣同一組數字不同順序會被重複計算
- 狀態轉移：
dp[i] += dp[i - num]（對每個num in nums）
Approaches
1. Top-Down Memoization — O(target * n) / O(target)
- Idea: 遞迴嘗試每個
num，記憶化子問題 - Time:
O(target * n) - Space:
O(target)
class Solution {
fun combinationSum4(nums: IntArray, target: Int): Int {
val memo = IntArray(target + 1) { -1 }
fun dp(rem: Int): Int {
if (rem == 0) return 1
if (rem < 0) return 0
if (memo[rem] != -1) return memo[rem]
var count = 0
for (num in nums) {
count += dp(rem - num)
}
memo[rem] = count
return count
}
return dp(target)
}
}⭐ 2. Bottom-Up DP — O(target * n) / O(target)
- Idea: 自底向上填表，外層遍歷目標值，內層遍歷所有可用數字
- Time:
O(target * n) - Space:
O(target)
class Solution {
fun combinationSum4(nums: IntArray, target: Int): Int {
val dp = IntArray(target + 1)
dp[0] = 1
for (i in 1..target) {
for (num in nums) {
if (num <= i) {
dp[i] += dp[i - num]
}
}
}
return dp[target]
}
}🔑 Takeaways
- Pattern: 排列型完全背包 — 外層遍歷容量，內層遍歷物品，以計算排列數
- Key trick: 組合 vs 排列的差別在於迴圈順序：外層物品內層容量 = 組合數；外層容量內層物品 = 排列數