LeetCode 377 Combination Sum IV

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?

题目大意：

求所有可能组合的和等于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)