動機
有用硬幹的感覺
Problem
Given an array of distinct integers nums
and a target integer target
, return the number of possible combinations that add up to target
.
The answer is guaranteed to fit in a 32-bit integer.
Example 1:
Input: nums = [1,2,3], target = 4Output: 7Explanation: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 = 3Output: 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?
Sol
f(cnt)
代表cnt的最大組合數,接下來就是遞迴+記憶法
class Solution:
@functools.cache
def f(self,cnt):
if cnt < 0:
return 0
elif cnt == 0:
return 1
else:
ret = 0
for n in self.nums:
ret += self.f(cnt-n)
return ret
def combinationSum4(self, nums: List[int], target: int) -> int:
self.nums = nums
return self.f(target)