377. 组合总和 IV（Combination Sum IV）

频次 ★★★ · 难度 🟡 · 高频：字节

题目

不同整数数组 nums，找出总和为 target 的元素组合个数（顺序不同的序列视为不同组合）。

示例：

输入: 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)）

思路

完全背包求排列数：dp[i] 表示凑成 i 的排列数。

dp[i] += dp[i - num] for each num ≤ i。

关键：外层遍历金额 i，内层遍历硬币 num。这与 518 题（组合数）内外层相反。因为排列考虑顺序，外层金额意味着”走到金额 i 时，最后一步可以用任意硬币”，这样不同顺序会被重复计数成不同方案。

代码

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;                               // 凑 0 有一种方式
    for (int i = 1; i <= target; i++) {       // 外层：金额（排列数）
        for (int num : nums) {                // 内层：硬币
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
}

复杂度

• 时间：O(target × n)，n = nums 长度
• 空间：O(target)

边界条件

• target = 0：返回 1
• nums 中有超出 target 的数：跳过
• 结果可能溢出：题目保证结果在 int 范围内，但中间量可能超过，实际提交时注意

变式

• 518. 零钱兑换 II：求组合数——内外层交换
• 322. 零钱兑换：求最少硬币数——完全背包最值

易错点

• 内外层顺序是核心：外层金额 = 排列，外层硬币 = 组合。这道题和 518 的唯一区别
• 题目虽然叫”组合总和 IV”，但实际求的是排列数（顺序不同算不同）
• 注意 dp 数组可能越界，LeetCode 题目保证结果在 int 范围，但中间值可能溢出（C++ 需用 unsigned int，Java 可以）

面试追问

• 为什么叫”组合”但求的是排列？ LeetCode 中文翻译问题，英文题名 Combination Sum IV，但题目描述明确说”顺序不同的序列视为不同组合”
• 和 518 的区别？ 只有内外层循环顺序不同，面试中经常对比考察

关联题

• 同套路：518. 零钱兑换 II —— 组合数（内外层交换）
• 进阶：322. 零钱兑换 —— 最少硬币数
• 知识点：完全背包排列 vs 组合见动态规划