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(intj0;jtarget;j){// 背包for(inti0;inums.length;i){// 物品if(jnums[i]){dp[j]dp[j-nums[i]];}}}为什么这样写层级含义外层j枚举总金额内层i枚举所有可用的数字✅每一个金额都可以由任意数字结尾✅ 自然形成排列顺序差异✅ 得到的是排列数❌ 错误的遍历顺序组合数for(inti0;inums.length;i){for(intjnums[i];jtarget;j){dp[j]dp[j-nums[i]];}}❌ 会限制数字使用顺序❌ 只能得到组合数 记忆口诀非常重要完全背包组合数先物品后背包排列数先背包后物品✅ AC 代码JavaclassSolution{publicintcombinationSum4(int[]nums,inttarget){int[]dpnewint[target1];dp[0]1;// 凑成 0 有 1 种方式// 先遍历背包for(intj0;jtarget;j){// 再遍历物品for(inti0;inums.length;i){if(jnums[i]){dp[j]dp[j-nums[i]];}}}returndp[target];}}⏱️ 复杂度分析指标复杂度时间复杂度O(target × nums.length)空间复杂度O(target) 与「零钱兑换 II」的对比题目518. 零钱兑换 II377. 组合总和 IV是否无限使用✅✅是否区分顺序❌ 不区分✅ 区分遍历顺序先物品先背包DP 含义组合数排列数✅ 一句话总结完全背包 排列计数 外层金额、内层物品正序遍历。