377. 组合总和 Ⅳ

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4

Output: 7

Explanation:

The possible combination ways are:

(1, 1, 1, 1)

(1, 1, 2)

(1, 2, 1)

(1, 3)

(2, 1, 1)

(2, 2)

(3, 1)

Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3

Output: 0

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

题目大意

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

题目数据保证答案符合 32 位整数范围。

示例 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 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

进阶： 如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

解题思路

思路一：动态规划

• 状态定义:
  用 dp[i] 表示和为 i 的所有组合数。
• 状态转移:
  对于每个可能的和 i，遍历数组 nums，如果 i >= num，则可以通过 dp[i - num] 推导出 dp[i]：

  dp[i] += dp[i - num];
  

• 初始条件:
  dp[0] = 1 表示凑成和为 0 的方式只有一种，即不选任何元素。

复杂度分析

• 时间复杂度: O(target * n)，其中 n 是数组长度。
• 空间复杂度: O(target)，存储 DP 数组。

---

思路二：递归记忆化搜索

• 思路:
  使用递归求解 helper(n) 表示凑成和为 n 的组合数。如果子问题 helper(n - nums[i]) 已经计算过，则直接返回缓存值，避免重复计算。
• 状态转移:

  helper(n) = sum(helper(n - nums[i])) for all nums[i] <= n
  

• 初始条件:
  dp[0] = 1 同样表示凑成和为 0 的方式只有一种。
• 剪枝:
  若 n < nums[i] 则跳过递归调用。

复杂度分析

• 时间复杂度: O(target * n)，每个子问题仅计算一次。
• 空间复杂度: O(target)，由于递归栈和缓存数组占用空间。

代码

迭代动态规划

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function (nums, target) {
	const dp = new Array(target + 1).fill(0);
	dp[0] = 1;
	for (let i = 1; i <= target; i++) {
		for (let num of nums) {
			if (i >= num) {
				dp[i] += dp[i - num];
			}
		}
	}
	return dp[target];
};

递归记忆化搜索

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function (nums, target) {
	const dp = new Array(target + 1).fill(-1);
	dp[0] = 1;

	const helper = (n) => {
		if (dp[n] !== -1) return dp[n];
		let res = 0;
		for (let num of nums) {
			if (n >= num) {
				res += helper(n - num);
			}
		}
		dp[n] = res;
		return res;
	};

	return helper(target);
};

相关题目

题号	标题	题解	标签	难度	力扣
39	组合总和	[✓]	数组 回溯	🟠	🀄️ 🔗
2787	将一个数字表示成幂的和的方案数		动态规划	🟠	🀄️ 🔗