LeetCode 377：组合总和 Ⅳ（Combination Sum IV）—— 题解 ✅

LeetCode 377：组合总和 Ⅳ（Combination Sum IV）—— 题解 ✅

📖 内容概要

给定一个由不同整数组成的数组nums和一个目标整数target，
计算并返回所有可能的组合个数，使得这些整数的和为target。

✅元素可重复使用
✅顺序不同的序列视为不同组合
✅ 本质是完全背包 + 排列计数

💡 解题思路

一、问题本质

• 数字可以无限使用 ✅
• [1,1,2]、[1,2,1]、[2,1,1]算三种方案✅

👉 这是一个排列问题（Permutation）

二、DP 定义

dp[j]=凑成金额 j 的排列数

三、状态转移方程

dp[j]+=dp[j-nums[i]]

含义：

• 使用nums[i]作为最后一个数字
• 新增方案数 = 凑成j - nums[i]的方案数

🔥 核心重点：遍历顺序（本题灵魂）

✅ 正确的遍历顺序（排列数）

for(intj=0;j<=target;j++){// 背包for(inti=0;i<nums.length;i++){// 物品if(j>=nums[i]){dp[j]+=dp[j-nums[i]];}}}

为什么这样写？

✅每一个金额都可以由任意数字结尾
✅ 自然形成排列顺序差异
✅ 得到的是排列数

❌ 错误的遍历顺序（组合数）

for(inti=0;i<nums.length;i++){for(intj=nums[i];j<=target;j++){dp[j]+=dp[j-nums[i]];}}

❌ 会限制数字使用顺序
❌ 只能得到组合数

🔑 记忆口诀（非常重要）

完全背包

• 组合数：先物品，后背包
• 排列数：先背包，后物品

✅ AC 代码（Java）

classSolution{publicintcombinationSum4(int[]nums,inttarget){int[]dp=newint[target+1];dp[0]=1;// 凑成 0 有 1 种方式// 先遍历背包for(intj=0;j<=target;j++){// 再遍历物品for(inti=0;i<nums.length;i++){if(j>=nums[i]){dp[j]+=dp[j-nums[i]];}}}returndp[target];}}

⏱️ 复杂度分析

🔍 与「零钱兑换 II」的对比

✅ 一句话总结

完全背包 + 排列计数 = 外层金额、内层物品，正序遍历。