LeetCode LCR 104. 组合总和 Ⅳ

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 104. 组合总和 Ⅳ

题意分析

给一个各元素互不相同的正整数数组 nums 和目标值 target，问从 nums 中取数（每个数可以取任意多次）凑出 target 的方案有多少种。题面里最要命的一句话是：顺序不同的序列被视作不同的组合。(1,3) 和 (3,1) 算两种。

这句话把题目从「组合计数」变成了「排列计数」，也直接决定了后面双层循环的先后顺序——这是本题唯一但极致命的考点，名字里的「组合」二字其实是个陷阱。

其余信号都很温和：元素互不相同，所以不必去重；元素都是正数，所以和是严格递增的，不会出现「加了一个数反而变小」的情形；target ≤ 1000、nums[i] ≤ 1000，值域小到可以直接当下标；每个数可取无限次，指向「无限取用」的取数模型。

返回的是方案数量，不是具体方案，所以不需要记录路径，状态里只留一个计数即可。题目还保证答案落在 32 位有符号整数范围内，这条保证很重要——它允许我们放心用 int 累加而不做取模。

边界：target 本身可能恰好等于某个元素，此时长度为 1 的序列也算一种；某些 target 完全凑不出（比如 nums = [2]、target = 3），此时答案是 0 而不是 -1。至于「如果允许负数会怎样」，那会让序列可以无限增长、方案数变成无穷，是面试官常追问的进阶点。

解法：动态规划递推

核心思路

暴力做法是回溯：每一层从 nums 里挑一个数减掉剩余目标，减到 0 就计一种方案。因为顺序有区分，每一层都要把所有元素都试一遍，搜索树的分支是 n、深度是 target / min(nums)，方案数本身就可能是天文数字，逐条枚举必然超时。

瓶颈在于同一个「剩余目标」被反复展开。凑 4 时，先取 1 再取 2、和先取 2 再取 1，都会落到「还剩 1」这个子问题上；而「还剩 1 有多少种凑法」是一个与「之前怎么走过来的」完全无关的定值。把剩余目标合并成状态，指数树立刻塌成一维递推。

观察到这一点，状态定义为：dp[i] = 凑出总和恰好为 i 的、有序序列的个数。这里必须把「有序」两个字写进定义里，否则后面的循环顺序就无从判断。

初始状态 dp[0] = 1：空序列是凑出 0 的唯一方案。它是所有计数的种子，必须是 1 而不是 0。

转移方程：dp[i] = Σ dp[i - num]，对所有满足 num ≤ i 的 num 求和。它的读法是按「序列的最后一个数」分类：一个和为 i 的序列，它的末位一定是某个 num，去掉末位后剩下的是一个和为 i - num 的合法序列，且不同的末位产生的序列必然不同。这正是「有序」语义的直接体现——如果按「第一个数」或「用了哪些数」分类，就变成组合计数了。

由此推出循环顺序：外层遍历目标 i（从小到大），内层遍历元素 num。因为计算 dp[i] 时需要所有 dp[i - num] 都已经就绪，而这些下标全都小于 i，所以外层必须是递增的容量维。反过来若把元素放在外层，就等于强制规定「小编号的元素只能出现在大编号元素之前」，得到的是组合数（即 518 题的答案）而不是排列数。

最终答案是 dp[target]。

解题步骤

开长度 target + 1 的整型数组 dp，全部初始化为 0。为什么长度要 +1：下标需要覆盖 0 到 target。为什么初值是 0：dp[i] 是计数，尚未发现任何方案时就是 0 种。

置 dp[0] = 1。为什么：空序列是和为 0 的唯一方案，它是所有转移的源头。若写成 0，整张表恒为 0，任何输入都会返回 0。

外层从 i = 1 递增到 target。为什么必须递增：转移只依赖比 i 小的下标，递增才能保证依赖已算好。为什么容量在外层：这是「排列计数」的标志——每一个 i 都要把所有元素都当作末位试一遍，从而允许同一个元素在不同位置反复出现、也允许不同元素以任意先后顺序组合。

内层遍历每个 num，若 i >= num 则执行 dp[i] += dp[i - num]。为什么要判 i >= num：num > i 时这个数不可能作为末位（会让和超过 i），且 i - num 会是负下标。为什么用 += 而不是 max 之类：本题求的是方案总数，各个末位对应的方案两两互斥，直接相加即可。

返回 dp[target]。为什么：它的含义就是「和恰为 target 的有序序列个数」，正是题目所求；凑不出时它自然停在 0，不需要额外的不可达判断。

以 nums = [1, 2, 3]、target = 4 走一遍。初始 dp = [1, 0, 0, 0, 0]。

i = 1：只有 num = 1 满足 1 >= num，dp[1] += dp[0] = 1。dp = [1, 1, 0, 0, 0]。对应序列 (1)。

i = 2：num = 1 时 dp[2] += dp[1] = 1（末位是 1，前缀是 (1)）；num = 2 时 dp[2] += dp[0] = 1（末位是 2，前缀是空）。dp[2] = 2，对应 (1,1) 与 (2)。

i = 3：num = 1 加上 dp[2] = 2；num = 2 加上 dp[1] = 1；num = 3 加上 dp[0] = 1。dp[3] = 4，对应 (1,1,1)、(2,1)、(1,2)、(3)。注意 (2,1) 和 (1,2) 被分别记入了不同的末位分类，这正是排列语义生效的地方。

i = 4：num = 1 加上 dp[3] = 4；num = 2 加上 dp[2] = 2；num = 3 加上 dp[1] = 1。dp[4] = 7。

返回 7，对应 (1,1,1,1)、(1,1,2)、(1,2,1)、(2,1,1)、(2,2)、(1,3)、(3,1)，与题目样例一致。

对照一下把两层循环调换的后果：若外层遍历 num、内层遍历 i，dp[4] 会得到 4，对应 {1,1,1,1}、{1,1,2}、{2,2}、{1,3} 四个无序集合——(1,2,1)、(2,1,1)、(3,1) 都被合并掉了。同一份转移方程，循环顺序一换答案就从 7 变成 4，这就是本题真正要考的东西。

代码实现

class Solution {

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        // 空序列是凑出 0 的唯一方案。
        dp[0] = 1;
        // 容量在外层、元素在内层：按「序列末位」分类，统计的是排列数。
        for (int i = 1; i <= target; ++i) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}

func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    // 空序列是凑出 0 的唯一方案。
    dp[0] = 1
    // 容量在外层、元素在内层：按「序列末位」分类，统计的是排列数。
    for i := 1; i <= target; i++ {
        for _, num := range nums {
            if i >= num {
                dp[i] += dp[i-num]
            }
        }
    }
    return dp[target]
}

复杂度分析

时间复杂度：$O(target \cdot n)$，其中 $n$ 是元素个数。凭什么：外层扫 target 个容量，内层扫 $n$ 个元素，循环体只有一次比较加一次累加。本题上界约 $1000 \times 200 = 2 \times 10^5$。

空间复杂度：$O(target)$。凭什么：只维护一维长度为 target + 1 的计数数组，没有递归栈也没有额外的哈希结构。

关键点总结

「顺序不同算不同方案」= 排列数 = 容量在外层、元素在内层；「顺序不同算同一方案」= 组合数 = 元素在外层、容量在内层。这一对口诀是背包计数题的分水岭，面试时要能立刻判断题目落在哪一边。

判断循环顺序的方法不是背结论，而是问自己「转移是按序列的哪个位置分类的」：按末位分类必然要求容量在外层。能讲出这层理由，遇到变形题也不会记混。

计数型 DP 的种子恒为 dp[0] = 1，代表空方案；这与可行性 DP 的 dp[0] = true、最优化 DP 的 dp[0] = 0 是同一位置的三种取值语义。

元素互不相同这个条件省掉了去重逻辑；若允许重复元素，同一个值会被当作两个不同的末位重复计数，需要先去重。

面试视角：本题几乎必然被追问「如果 nums 含负数会怎样」。标准回答是——负数会让序列长度无上界（例如 [-1, 1] 可以无限延长），方案数变成无穷，必须额外限制序列长度，状态要升维成 dp[长度][和]。

同样是「无限取用」，本题求排列数、518 求组合数、322 求最少枚数，三者共用一张一维表，区别只在初值语义与循环顺序，可以放在一起对照记忆。

易错点总结

两层循环写反（元素在外、容量在内）：nums = [1, 2, 3]、target = 4 会返回 4 而不是 7，因为 (1,2) 与 (2,1) 被算成同一种。这是本题占比最高的错误。

dp[0] 忘记置 1：nums = [1]、target = 1 时整张表恒为 0，返回 0 而正确答案是 1。

漏掉 i >= num 的判断：nums = [3]、target = 1 时访问 dp[-2]，Java 抛 ArrayIndexOutOfBoundsException，Go 直接 panic。

把 i >= num 写成 i > num：nums = [4]、target = 4 时长度为 1 的序列 (4) 被漏掉，返回 0 而正确答案是 1。

外层从 i = 0 开始：i = 0 时若 nums 含 0 会自我累加，且会把 dp[0] 从 1 改成别的值，污染整张表的种子；从 i = 1 起步天然规避。

数组开成 new int[target]：nums = [1]、target = 1 时最后访问 dp[1] 越界，长度必须是 target + 1。

把 += 写成 =：nums = [1, 2]、target = 3 时 dp[3] 只保留最后一个元素的贡献，返回 1 而正确答案是 3。

担心溢出而对结果取模：题目保证答案在 32 位整数内，擅自对 $10^9+7$ 取模会让 nums = [1, 2, 3]、target = 32 这类本来就没超范围的用例返回与期望不符的值。

误以为可以套用「组合数」的去重技巧（比如内层从当前下标起遍历）：nums = [1, 2]、target = 3 会返回 2 而不是 3，因为限制了元素的相对顺序。

相似题目

题目	难度	考察点
377. 组合总和 Ⅳ	中等	与本题同题，可直接套用同一份代码
518. 零钱兑换 II	中等	求组合数，循环顺序与本题恰好相反，是最佳对照实验
322. 零钱兑换	中等	同为无限取用，但求最少枚数，转移从求和变成取 `min` 并需哨兵
279. 完全平方数	中等	可取的数需要现场生成，且求的是最少个数而非方案数
70. 爬楼梯	简单	就是 `nums = [1, 2]` 的本题特例，可用来验证排列语义是否理解正确
1449. 数位成本和为目标值的最大数字	困难	成本必须恰好用完，且比较的是拼接后数字的大小而非数量
面试题 08.11. 硬币	中等	求组合数并要求取模，面额固定，可对照体会取模时机