企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文围绕 AlgoNote 仓库中 0377. 组合总和 IV 题解展开，剖析一类容易被忽略的背包 DP 变体：完全背包求方案数，但组合内元素顺序不同算不同方案。读完本文，你将掌握「外层遍历总和、内层遍历元素」的循环设计依据，理解它与「零钱兑换 II」等经典完全背包方案数问题的本质差异，并能直接复现代码解决同型面试题。

一、题目回顾：从 nums 中选数凑 target，顺序不同算不同组合

题目描述：给定一个由不同整数组成的数组nums和一个目标整数target，从nums中找出并返回总和为target的元素组合个数。

关键约束（原题解文档中给出的数据范围）：

• 题目数据保证答案符合 32 位整数范围；
• 1 <= nums.length <= 200；
• 1 <= nums[i] <= 1000；
• nums中的所有元素互不相同；
• 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：完全背包求方案数，且考虑顺序（外层总和、内层物品）。

将这几道题对照研读，就能彻底打通「完全背包 + 方案数」的两大分支：

如需进一步追溯理论，可研读仓库中完全背包讲解文档（含状态转移方程优化与滚动数组推导），以及 Pack-ProblemVariants.py 中关于“求方案总数”“求最优方案数”“求具体方案”等变体的完整 Python 实现，它们共同构成了从 0-1 背包到完全背包、从求最值到求方案数的完整方法论。

一句话总结：组合总和 IV 用“外层总和、内层元素”的循环次序，把完全背包的方案数统计从“组合计数”升级为“排列计数”，是背包 DP 中循环次序决定语义的经典案例。

• 教程
• 文档
• 知识库