LeetCode 377 Combination Sum IV

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>Input: nums = [9], target = 3 Output: 0 </pre>

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?

</div>

题目大意：

求所有可能组合的和等于target。元素可以复用且顺序在组合中可以任意。

LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列 LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合

解题思路：

这题似组合又似排列，是组合的结果再全排列。求种数另一种的方法是DP. dp[n]为target=n所有的所有组合种数。属于数值->个数型DP
递归公式

dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]

解题步骤：

N/A

注意事项：

1. dp[i + nums[j]] += dp[i] 而不是dp[i] + 1
2. dp[0] = 1表示数值为0，可以不用任何数就能获得，所以是1种
3. 先排序，否则如[3, 1, 2, 4]，返回dp[1] = 0, 但应该是dp[1] = 1

Python代码：

# dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]
def combinationSum4(self, nums: List[int], target: int) -> int:
	nums.sort() # remember
	dp = [0] * (target + 1)
	dp[0] = 1
	for i in range(len(dp)):
		for j in range(len(nums)):
			if i + nums[j] > target:
				break
			dp[i + nums[j]] += dp[i] # remember no +1
	return dp[-1]

算法分析：

时间复杂度为O(n*target)，空间复杂度O(target)