# leetcode 377. Combination Sum IV (python)

2022-08-06 11:54:04big wang

### 描述

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 = , target = 3
Output: 0

Note:

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

### 解析

This question can obviously use memoization DFS to complete the answer,Our defining function dfs(x) 为从 nums Keep picking numbers（可以重复）可以构成 x 的方法数,As shown in example 1,我们要求 dfs(4) ,Suppose I get the first number from nums 中选择了 1 ,So I'm going to ask dfs(3) ,Suppose I choose the first number 2 ,So I'm going to ask dfs(2) ,Suppose I choose the first number 3 ,So I'm going to ask dfs(1) ,所以 dfs(4) = dfs(3) + dfs(2) + dfs(1) ,然后递归求解 dfs(3) 、dfs(2) 、dfs(1) .Many operations are repeated in the recursive process,We store these results in m 中.

Of course memoized DFS The solution has been written,Then you can continue to write the dynamic programming solution,The code is written differently,但是核心都是一样的.

### 解答

``````class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
self.m = [-1] * (target + 1)
self.m = 1
def dfs(total):
if total < 0:
return 0
if self.m[total] != -1:
return self.m[total]
result = 0
for n in nums:
result += dfs(total - n)
self.m[total] = result
return result
return dfs(target)

### 运行结果

``````Runtime: 79 ms, faster than 23.53% of Python3 online submissions for Combination Sum IV.
Memory Usage: 14.1 MB, less than 18.29% of Python3 online submissions for Combination Sum IV.

### 原题链接

leetcode.com/problems/co…