377. Combination Sum IV

Medium

Description

給定一個不重複的正整數陣列 nums 和一個目標值 target，求湊成 target 的排列數（不同順序算不同組合）。

Example:

Input: nums = [1,2,3], target = 4 Output: 7

Intuition#

類似 Coin Change 但求排列數 — 外層迴圈遍歷目標值，內層遍歷 nums。

和 Coin Change 不同的是：不同順序算不同方案（排列而非組合）
dp[i] = 湊成金額 i 的排列數
外層遍歷金額，內層遍歷 nums，這樣同一組數字不同順序會被重複計算
狀態轉移：dp[i] += dp[i - num]（對每個 num in nums）

Approaches#

1: Top-Down Memoization#

概念: 遞迴嘗試每個 num，記憶化子問題
時間複雜度: O(target * n)
空間複雜度: 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)

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: 排列型完全背包 — 外層遍歷容量，內層遍歷物品，以計算排列數
關鍵技巧: 組合 vs 排列的差別在於迴圈順序：外層物品內層容量 = 組合數；外層容量內層物品 = 排列數