🎯 一句話理解

• 求組合數（不計順序） → 外層遍歷物品，內層遍歷背包容量

• 求排列數（計順序） → 外層遍歷背包容量，內層遍歷物品

---

🎲 舉例說明

假設有硬幣 [1, 2, 3]，目標金額是 4，要求湊成的方法數：

1. 組合數（順序無關）：

比如：[1, 2, 1] 和 [2, 1, 1]、[1, 1, 2] 視為同一種方案，因為它們元素一樣，只是順序不同。

for i := 0; i < len(nums); i++ {       // 物品在外層for j := nums[i]; j <= target; j++ { // 容量在內層dp[j] += dp[j - nums[i]]}
}

這種寫法只會把每組物品組合一次，不考慮排列方式。

---

2. 排列數（順序有關）：

比如：[1, 2, 1]、[2, 1, 1]、[1, 1, 2] 視為3種不同方案。

for j := 0; j <= target; j++ {       // 容量在外層for i := 0; i < len(nums); i++ { // 物品在內層if j >= nums[i] {dp[j] += dp[j - nums[i]]}}
}

這樣每次容量增加時，都會把所有可放的物品都考慮一遍 ? 排列自然產生了。

---

? 總結對比

目標	外層循環	內層循環	特點
組合數（無序）	遍歷物品 i	遍歷容量 j	順序不會重復
排列數（有序）	遍歷容量 j	遍歷物品 i	會計算所有順序

---

🧠 記憶口訣

🎯 組合外層物品，排列外層背包。

詳細解釋?組合外層物品，排列外層背包

🎯 問題背景

我們有硬幣 coins = [1, 2, 3]，目標是金額 4。我們想知道有多少種方案湊出金額 4：

---

🧮 什么是組合數（不計順序）？

• 組合數不區分順序：[1,1,2]、[2,1,1]、[1,2,1] 是同一種組合。

• 所以我們只想知道「有哪些組合方式」，不在意順序。

---

? 為什么組合數要先遍歷物品？

我們看以下代碼：

dp := make([]int, target+1)
dp[0] = 1
for i := 0; i < len(coins); i++ {       // 外層：物品（硬幣）for j := coins[i]; j <= target; j++ { // 內層：背包容量dp[j] += dp[j - coins[i]]}
}

🌱 核心思想：

每次選一個硬幣coins[i]，我們更新所有能放它的位置，但每個 dp[j] 只會累加來自當前物品之前的組合。

這樣做的結果是：

• 所有組合只計算一次，避免了順序重復。

---

?? 舉個例子

第一層循環：i = 0（coin = 1）

更新 dp[1], dp[2], dp[3], dp[4]，只用 1 元硬幣。

此時：

dp = [1 1 1 1 1]

表示只用 1 元可以組成的方法數，只有一種 [1,1,1,1]。

---

第二層循環：i = 1（coin = 2）

我們再用 2 元更新，但只能在原有的基礎上增加。

• dp[2] += dp[0] → [2]

• dp[3] += dp[1] → [1,2]

• dp[4] += dp[2] → [2,2]

更新后：

dp = [1 1 2 2 3]

說明方法數是：[1,1,1,1], [1,1,2], [2,2], 不會重復 [2,1,1]、[1,2,1] 等順序。

---

📦 如果調換循環順序會怎樣？

比如改為這樣：

for j := 0; j <= target; j++ {for i := 0; i < len(coins); i++ {if j >= coins[i] {dp[j] += dp[j - coins[i]]}}
}

這時每個 j 都會嘗試所有硬幣，所以：

• dp[3] 會通過 [1,2]，也會通過 [2,1]，兩次都被算入。

• 所以是排列數（考慮順序）。

---

🔁 總結

目標	外層循環	結果特性	會不會重復順序
組合數	物品在外	不計順序	不會
排列數	背包在外	順序不同都算	會