教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文围绕 AlgoNote 仓库中 0377. 组合总和 IV 题解展开剖析一类容易被忽略的背包 DP 变体完全背包求方案数但组合内元素顺序不同算不同方案。读完本文你将掌握「外层遍历总和、内层遍历元素」的循环设计依据理解它与「零钱兑换 II」等经典完全背包方案数问题的本质差异并能直接复现代码解决同型面试题。一、题目回顾从 nums 中选数凑 target顺序不同算不同组合题目描述给定一个由不同整数组成的数组nums和一个目标整数target从nums中找出并返回总和为target的元素组合个数。关键约束原题解文档中给出的数据范围题目数据保证答案符合 32 位整数范围1 nums.length 2001 nums[i] 1000nums中的所有元素互不相同1 target 1000。示例 1输入nums [1,2,3], target 4 输出7 解释 所有可能的组合为 (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意顺序不同的序列被视作不同的组合。示例 2输入nums [9], target 3 输出0示例 1 中(1, 2, 1)与(2, 1, 1)虽然元素集合相同、出现次数相同但因为排列顺序不同而被计为两种方案示例 2 则说明当数组元素无法凑出目标时答案为 0。二、问题归类完全背包求方案数的“顺序敏感”变体原题解开篇即指出本题是**「完全背包问题求方案数」的变形**其特殊之处在于——方案中不同的物品顺序代表不同方案。2.1 为什么是“完全背包”从题意看nums中的每个元素可以重复使用任意多次示例 1 中1出现了 4 次这正是完全背包的核心特性。AlgoNote 的完全背包讲解文档将其定义为给定若干种物品每种物品数量不限求在容量限制下背包的最大价值而仓库中的 Pack-CompletePack.py 展示了完全背包三种递进解法二维基本思路、状态转移方程优化、滚动数组优化其滚动数组版本采用正序枚举容量for i in range(1, size 1): for w in range(weight[i - 1], W 1): dp[w] max(dp[w], dp[w - weight[i - 1]] value[i - 1])正序枚举的目的正是为了让当前种类的物品能够被反复选取对应到本题就是允许nums中的数字被无限次使用。2.2 与“顺序不敏感”方案数问题的对比循环次序决定一切「完全背包求方案数」在 AlgoNote 仓库中有完整的参考实现见 Pack-ProblemVariants.py 中的completePackNumbers方法def completePackNumbers(self, weight: [int], value: [int], W: int): size len(weight) dp [0 for _ in range(W 1)] dp[0] 1 # 枚举前 i 种物品 for i in range(1, size 1): # 正序枚举背包装载重量 for w in range(weight[i - 1], W 1): dp[w] dp[w] dp[w - weight[i - 1]] return dp[W]这段代码的循环结构是「外层枚举物品种类、内层枚举总和」。在这种次序下[1, 3]与[3, 1]只会被统计 1 次——因为物品维在外层每种数字在生成方案时天然被“排列”在固定的相对顺序中这正是「零钱兑换 II」0518所采用的模型不考虑硬币的选取顺序。而本题要求顺序不同即为不同方案。原题解文档用一句话点破本质差异在「完全背包问题求方案数」中凑成总和为 4 的方案[1, 3]算 1 种方案但在本题中[1, 3]、[3, 1]算 2 种方案数。三、核心突破交换循环次序——外层总和、内层元素要让顺序敏感就必须在考虑某个总和w时把nums中的全部元素都作为最后一个被加入的候选。这对应到循环关系上就是将总和w的遍历放到外侧循环将nums数组元素的遍历放到内侧循环for w in range(target 1): for i in range(1, len(nums) 1): # 状态转移这个双层循环骨架正是原题解给出的解题起点也是理解本题与经典完全背包方案数问题的分水岭外层枚举总和w相当于枚举“当前正在拼凑的目标值”从 0 一路增长到target内层枚举nums[i-1]在拼凑总和w时穷举所有可能“最后一步放入”的数字从而把(1, 2, 1)与(2, 1, 1)这类仅顺序不同的排列全部纳入计数。为了更直观地理解可以对比仓库中的两组实现0-1 背包在滚动数组优化下需要逆序枚举容量见 Pack-ZeroOnePack.py 的zeroOnePackMethod2逆序是为了避免同一件物品被重复选择完全背包则改为正序枚举容量以支持无限次使用而本题在“完全背包正序”的基础上再进一步——把容量总和维度提到外层从而让每种数字在每个总和阶段都能“重新排队”统计出所有排列。四、动态规划设计五步走原题解采用标准的 DP 五步法组织以下逐一展开。4.1 阶段划分按照总和进行阶段划分即从小到大依次求解w 0, 1, ..., target对应的方案数。这与仓库中背包专题文档0-1 背包、完全背包中「以背包载重上限作为阶段」的思路一脉相承。4.2 定义状态定义状态dp[w]表示为凑成总和w的组合数。数组长度为target 1下标0 ~ target一一对应所有可能的和值。由于1 target 1000一维数组的空间开销完全可控。4.3 状态转移方程凑成总和为w的组合数 「不使用当前nums[i-1]、只使用之前整数凑成和为w的组合数」「使用当前nums[i-1]凑成和为w - nums[i-1]的方案数」。即dp[w] dp[w] dp[w - nums[i-1]]这里dp[w - nums[i-1]]表示在总和为w - nums[i-1]的所有既有方案末尾追加一个nums[i-1]。由于外层循环遍历的是总和而非物品追加位置是“末尾”而不同阶段追加出来的排列会在后续阶段继续参与转移最终覆盖所有顺序。代码层面转移前需要判断w nums[i-1]保证下标w - nums[i-1]非负同时由于转移依赖的是当前阶段同一次外层w循环内尚未完整更新的其他小和值方案内层对元素的无序遍历并不会引入错误计数——这正体现了外层总和、内层元素结构的数学含义。4.4 初始条件凑成总和0的组合数为1即dp[0] 1空序列视为一种方案是递推的“种子”。其余dp[w]w 0初始化为0表示尚未找到任何组合。4.5 最终结果根据状态定义dp[target]即为凑成目标整数target的组合总数直接返回即可。五、完整可运行代码与逐行注释原题解给出了如下参考实现这里补充完整注释以便直接复制使用class Solution: def combinationSum4(self, nums: List[int], target: int) - int: size len(nums) # dp[w]凑成总和 w 的组合数顺序敏感排列计数 dp [0 for _ in range(target 1)] dp[0] 1 # 空序列凑成总和 0作为递推起点 # 外层枚举总和 w从 0 逐步增长到 target for w in range(target 1): # 内层枚举 nums 中的每个元素作为最后一步放入的候选 for i in range(1, size 1): if w nums[i - 1]: # 在不使用 nums[i-1] 的既有方案 dp[w] 基础上 # 累加凑成 w - nums[i-1] 后追加 nums[i-1]产生的新排列 dp[w] dp[w] dp[w - nums[i - 1]] return dp[target]示例验证对nums [1,2,3]、target 4运行上述代码递推过程会依次得到dp[1]1、dp[2]2(1,1)、(2)、dp[3]4(1,1,1)、(1,2)、(2,1)、(3)、dp[4]7与题目给出的 7 种排列完全吻合。对nums [9]、target 3由于9 3永远无法加入dp[3] 0同样符合预期。六、复杂度分析与边界讨论时间复杂度O(n × target)其中n为数组nums的元素个数target为目标整数。外层target 1次、内层n次每次常数时间转移。空间复杂度O(target)仅需一个长度为target 1的一维数组。边界情况提示当target较大而nums元素较小时方案数可能迅速膨胀。题目已保证答案在 32 位整数范围内因此在 LeetCode 环境中无需额外取模若题目修改约束如target加大需要留意整数溢出风险。当nums中所有元素都大于target时所有dp[w]w 1保持为 0直接返回dp[target] 0与示例 2 行为一致。由于nums元素互不相同内层循环无需处理重复数字去重若输入允许重复元素则需要在状态定义上另行考虑去重策略本题不适用。七、从本题到整个“完全背包方案数”知识族本题在 AlgoNote 中归属于「完全背包问题」专题见分类题目列表中的「完全背包问题题目」一节同族题目还包括0279. 完全平方数完全背包求最少个数0322. 零钱兑换完全背包求最少硬币数0518. 零钱兑换 II完全背包求方案数但不考虑顺序外层物品、内层总和0377. 组合总和 IV完全背包求方案数且考虑顺序外层总和、内层物品。将这几道题对照研读就能彻底打通「完全背包 方案数」的两大分支模型循环结构计数语义代表题目组合顺序无关外层物品内层总和[1,3]与[3,1]算 1 种零钱兑换 II排列顺序敏感外层总和内层物品[1,3]与[3,1]算 2 种组合总和 IV如需进一步追溯理论可研读仓库中完全背包讲解文档含状态转移方程优化与滚动数组推导以及 Pack-ProblemVariants.py 中关于“求方案总数”“求最优方案数”“求具体方案”等变体的完整 Python 实现它们共同构成了从 0-1 背包到完全背包、从求最值到求方案数的完整方法论。一句话总结组合总和 IV 用“外层总和、内层元素”的循环次序把完全背包的方案数统计从“组合计数”升级为“排列计数”是背包 DP 中循环次序决定语义的经典案例。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐动态规划完全背包问题详解 - itcharge/LeetCode-Py项目解析动态规划完全背包问题详解 itcharge/LeetCode Py项目解析 引言为什么完全背包问题如此重要 在算法面试中动态规划Dynamic Prog教程文档知识库背包问题进阶指南混合背包、分组背包与二维费用背包的动态规划解法AlgoNote背包问题进阶指南混合背包、分组背包与二维费用背包的动态规划解法AlgoNote 本篇技术指南以「算法通关手册」AlgoNote 仓库的 08_09_kna教程文档知识库doocs/leetcode 题解精讲《程序员面试金典》面试题 08.11 硬币——完全背包动态规划求组合数doocs/leetcode 题解精讲《程序员面试金典》面试题 08.11 硬币——完全背包动态规划求组合数 本文基于 doocs/leetcode http示例工程教程上一篇阴阳师自动化脚本终极指南3步完成智能游戏辅助配置下一篇3步解锁Windows远程桌面多用户连接RDP Wrapper终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考