377. 组合总和 Ⅳ

题目描述

输入一个由互不相同的正整数组成的数组 nums，以及目标值 target。

从 nums 中选数排成一个序列，每个数可以用任意多次，要求序列各项之和等于 target。同样的数按不同顺序排列，算作不同的序列。

返回满足条件的序列个数。题目保证结果在 32 位有符号整数范围内。

示例 1

输入：nums = [1,2,3], target = 4
输出：7

解释：共 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

解释：唯一的数 9 比 3 大，无法凑出。

数据范围

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中元素互不相同
1 <= target <= 1000

进阶：如果数组里允许出现负数，结果会有什么变化？需要再加上什么限制，问题才有意义？

解题思路：完全背包排列 DP

因为顺序有关，实际是在数“排列”。dp[t] 表示和为 t 的序列个数。按最后一个数 x 分类：去掉最后的 x，前面是和为 t-x 的任意序列，所以 dp[t] = ∑ dp[t-x]（x <= t）。dp[0] = 1 代表空序列。外层遍历 t、内层遍历 nums。

为什么正确

计算 dp[t] 时，dp[0..t-1] 已是最终值。

复杂度分析

时间 O(target · n)，空间 O(target)。

易错点

循环顺序不能写反：外层遍历 nums、内层遍历 t 算的是不计顺序的组合数（如零钱兑换 II）；中间结果可能超过 32 位，C++ 用 unsigned 或取模避免溢出报错。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for t in range(1, target + 1):
            for x in nums:
                if x <= t:
                    dp[t] += dp[t - x]
        return dp[target]

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int t = 1; t <= target; t++)
            for (int x : nums)
                if (x <= t)
                    dp[t] += dp[t - x];
        return dp[target];
    }
}

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long long> dp(target + 1, 0);
        dp[0] = 1;
        for (int t = 1; t <= target; t++)
            for (int x : nums)
                if (x <= t)
                    dp[t] += dp[t - x];
        return dp[target];
    }
};

func combinationSum4(nums []int, target int) int {
	dp := make([]uint64, target+1)
	dp[0] = 1
	for t := 1; t <= target; t++ {
		for _, x := range nums {
			if x <= t {
				dp[t] += dp[t-x]
			}
		}
	}
	return int(dp[target])
}

var combinationSum4 = function(nums, target) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    for (let t = 1; t <= target; t++)
        for (const x of nums)
            if (x <= t)
                dp[t] = (dp[t] + dp[t - x]) % 4294967296;
    return dp[target];
};

function combinationSum4(nums: number[], target: number): number {
    const dp: number[] = new Array(target + 1).fill(0);
    dp[0] = 1;
    for (let t = 1; t <= target; t++)
        for (const x of nums)
            if (x <= t)
                dp[t] = (dp[t] + dp[t - x]) % 4294967296;
    return dp[target];
}

载入编辑器，自己跑一遍 →

其他解法

两种方法的状态和转移完全相同：记忆化搜索自顶向下按需计算，主解法自底向上按 t 从小到大填表，没有递归开销。

解法 2：记忆化搜索时间 O(target · n)，空间 O(target)

定义 f(t) 为凑出和 t 的排列数，f(0) = 1。f(t) 等于所有 x ≤ t 的 f(t - x) 之和，因为排列的最后一个数可以是任意 x。用数组缓存已算出的 f(t)，每个 t 只计算一次。

从“最后一步选谁”自顶向下思考，递推式和题意一一对应。只计算从 target 出发可达的状态；但有递归开销，target 大时要注意栈深度。

import sys


class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        sys.setrecursionlimit(max(10000, target * 2 + 100))
        memo = {0: 1}

        def f(t):
            if t in memo:
                return memo[t]
            res = 0
            for x in nums:
                if x <= t:
                    res += f(t - x)
            memo[t] = res
            return res

        return f(target)

class Solution {
    private int[] memo;
    private boolean[] seen;

    public int combinationSum4(int[] nums, int target) {
        memo = new int[target + 1];
        seen = new boolean[target + 1];
        memo[0] = 1;
        seen[0] = true;
        return f(nums, target);
    }

    private int f(int[] nums, int t) {
        if (seen[t]) return memo[t];
        int res = 0;
        for (int x : nums)
            if (x <= t)
                res += f(nums, t - x);
        seen[t] = true;
        memo[t] = res;
        return res;
    }
}

class Solution {
    vector<unsigned long long> memo;
    vector<bool> seen;

    unsigned long long f(vector<int>& nums, int t) {
        if (seen[t]) return memo[t];
        unsigned long long res = 0;
        for (int x : nums)
            if (x <= t)
                res += f(nums, t - x);
        seen[t] = true;
        memo[t] = res;
        return res;
    }

public:
    int combinationSum4(vector<int>& nums, int target) {
        memo.assign(target + 1, 0);
        seen.assign(target + 1, false);
        memo[0] = 1;
        seen[0] = true;
        return f(nums, target);
    }
};

func combinationSum4(nums []int, target int) int {
	memo := make([]uint64, target+1)
	seen := make([]bool, target+1)
	memo[0], seen[0] = 1, true
	var f func(t int) uint64
	f = func(t int) uint64 {
		if seen[t] {
			return memo[t]
		}
		var res uint64
		for _, x := range nums {
			if x <= t {
				res += f(t - x)
			}
		}
		seen[t] = true
		memo[t] = res
		return res
	}
	return int(f(target))
}

var combinationSum4 = function(nums, target) {
    const memo = new Array(target + 1).fill(-1);
    memo[0] = 1;
    const f = (t) => {
        if (memo[t] !== -1) return memo[t];
        let res = 0;
        for (const x of nums)
            if (x <= t)
                res = (res + f(t - x)) % 4294967296;
        memo[t] = res;
        return res;
    };
    return f(target);
};

function combinationSum4(nums: number[], target: number): number {
    const memo: number[] = new Array(target + 1).fill(-1);
    memo[0] = 1;
    const f = (t: number): number => {
        if (memo[t] !== -1) return memo[t];
        let res = 0;
        for (const x of nums)
            if (x <= t)
                res = (res + f(t - x)) % 4294967296;
        memo[t] = res;
        return res;
    };
    return f(target);
}

动态规划专题的其他题目

查看动态规划全部题目 →