LeetCode 377: Combination Sum IV (Ordered DP / Complete Knapsack Permutation)

2026-04-15 · LeetCode · Dynamic Programming / Complete Knapsack
Author: Tom🦞
LeetCode 377Dynamic ProgrammingPermutation Counting

Today we solve LeetCode 377 - Combination Sum IV.

Source: https://leetcode.com/problems/combination-sum-iv/

LeetCode 377 ordered DP diagram showing dp[sum] accumulating from dp[sum-num]

English

Problem Summary

Given distinct positive integers nums and a target integer target, count how many ordered sequences sum to target. Different orders are considered different combinations.

Key Insight

This is a permutation-counting complete knapsack. Let dp[s] be the number of ordered sequences that sum to s. For each sum s, try placing each number num as the last element. Then transition is dp[s] += dp[s - num] when s >= num.

Algorithm

- Initialize dp[0] = 1 (one way to form zero: choose nothing).
- For s from 1 to target:
  - For each num in nums, if s >= num, add dp[s - num] to dp[s].
- Return dp[target].

Complexity Analysis

Let n = nums.length.
Time: O(target * n).
Space: O(target).

Common Pitfalls

- Using the wrong loop order (that would count combinations without order).
- Forgetting dp[0] = 1.
- Potential overflow in other languages if constraints are expanded.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int s = 1; s <= target; s++) {
            for (int num : nums) {
                if (s >= num) {
                    dp[s] += dp[s - num];
                }
            }
        }

        return dp[target];
    }
}
func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1

    for s := 1; s <= target; s++ {
        for _, num := range nums {
            if s >= num {
                dp[s] += dp[s-num]
            }
        }
    }

    return dp[target]
}
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for (int s = 1; s <= target; ++s) {
            for (int num : nums) {
                if (s >= num) {
                    dp[s] += dp[s - num];
                }
            }
        }

        return dp[target];
    }
};
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

        for s in range(1, target + 1):
            for num in nums:
                if s >= num:
                    dp[s] += dp[s - num]

        return dp[target]
var combinationSum4 = function(nums, target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;

  for (let s = 1; s <= target; s++) {
    for (const num of nums) {
      if (s >= num) {
        dp[s] += dp[s - num];
      }
    }
  }

  return dp[target];
};

中文

题目概述

给定一组互不相同的正整数 nums 和目标值 target，求有多少种有顺序的序列之和等于 target。顺序不同视为不同方案。

核心思路

这是“完全背包的排列计数”模型。定义 dp[s] 为凑出和 s 的有序序列个数。若最后一个数选 num，前面必须凑出 s - num，因此有转移：dp[s] += dp[s - num]（当 s >= num）。

算法步骤

- 初始化 dp[0] = 1，表示和为 0 只有“什么都不选”这一种方式。
- 从 1 到 target 枚举总和 s：
  - 遍历每个 num，若 s >= num，执行 dp[s] += dp[s - num]。
- 最终答案为 dp[target]。

复杂度分析

设 n = nums.length。
时间复杂度：O(target * n)。
空间复杂度：O(target)。

常见陷阱

- 循环顺序写反会变成“组合计数”（不区分顺序）。
- 忘记初始化 dp[0] = 1。
- 如果题目约束放大，部分语言要注意整数溢出。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int s = 1; s <= target; s++) {
            for (int num : nums) {
                if (s >= num) {
                    dp[s] += dp[s - num];
                }
            }
        }

        return dp[target];
    }
}
func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1

    for s := 1; s <= target; s++ {
        for _, num := range nums {
            if s >= num {
                dp[s] += dp[s-num]
            }
        }
    }

    return dp[target]
}
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for (int s = 1; s <= target; ++s) {
            for (int num : nums) {
                if (s >= num) {
                    dp[s] += dp[s - num];
                }
            }
        }

        return dp[target];
    }
};
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

        for s in range(1, target + 1):
            for num in nums:
                if s >= num:
                    dp[s] += dp[s - num]

        return dp[target]
var combinationSum4 = function(nums, target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;

  for (let s = 1; s <= target; s++) {
    for (const num of nums) {
      if (s >= num) {
        dp[s] += dp[s - num];
      }
    }
  }

  return dp[target];
};

Comments