## current position：Home>leetcode 377. Combination Sum IV (python)

# leetcode 377. Combination Sum IV (python)

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

携手创作,共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第11天,点击查看活动详情

### 描述

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
复制代码
```

Note:

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

### 解析

根据题意,Given an array of distinct integers nums 和一个目标整数 target ,Returns add up to target number of possible combinations.

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 中.

时间复杂度为 O(N\∗target),空间复杂度为 O(target).

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[0] = 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.
复制代码
```

### 原题链接

您的支持是我最大的动力

copyright notice

author[big wang],Please bring the original link to reprint, thank you.

https://en.pythonmana.com/2022/218/202208061137300699.html

## The sidebar is recommended

- Python's common modules of threading and Thread modules The first stage of thread implementation
- Blender Python Programming: Creating Emitting Materials
- Python multiprocessing
- How does python implement image edge detection
- Django paging method
- django regex
- How does Python represent time?2 modules, 3 ways, 1 text to understand~
- Modify column name and row index in pandas DataFrame
- [python pandas groupby]
- Python Daily Practice (New Question Bank of Niu Ke) - Day 20: Dictionary Practice

## guess what you like

[LeetCode brush questions] Hash table - some questions are implemented with built-in functions (with Python code)

[LeetCode brush questions] Linked list topic (1) (with Python code)

[Small case of python learning] Simulation system invasion to enhance interest

Getting Started with Python Basics - Essential Knowledge for Getting Started

How does Python represent time?2 modules, 3 ways, 1 text to get it~

Python office software automation, master openpyxl operation in 5 minutes

Introduction to Python Basics - Variables, Strings

[python2] remove the u in front of the unicode string

How to use the Python Color class to draw text

How to use Asyncio Python web programming

## Random recommended

- 27 Python artificial intelligence libraries have been sorted out, it is recommended to collect!
- [Python] Word2Vec predicts what will be left if I subtract 'love' from my 'life'
- When I export a pandas package, there is a problem. If I don't import it, there is no problem. Is this not enough memory?
- Python version 3.7.4 How can I install locust successfully?
- How does python use pyinstaller to package music into exe, that is, play background music when running the packaged program?
- Python use pyinstaller how to wrap up music exe, is to run a packaged program play background music?
- Rescue 007 of graph traversal application, detailed analysis of python version
- 27 Python artificial intelligence libraries have been sorted out, it is recommended to collect~
- pandas DataFrame data filtering (2)
- Python is how to represent time?- two modules, three ways, complete the ~ 1
- The definition of pycharm writing python code
- Problems defining functions in Python
- Python Socket Network Programming
- Django server running error
- Python image processing notes - image matching based on Harris corners (skimage)
- (Thirteen--1) Concurrent programming of python (thread, queue, process, coroutine, process thread coroutine comparison)
- (12) Python's memory management mechanism
- Python crawler entry case day07: Hippopx
- Django reports an error ModuleNotFoundError: No module named 'mysqlclient'
- Python study notes
- How to upgrade python? python3 version and install pip3
- [Python] 4-word summary for amateurs, PyCharm2022.2 Professional Edition improves development efficiency, basic settings and common shortcut keys (super practical) & basic knowledge of Python - CSDN 21-day learning challenge
- [Python Data Science Quick Start Series | 03] Playing with Data Extraction: Numpy Indexing and Slicing
- Python draws a curve experiment with matplotlib
- How to represent unequally spaced values with equally spaced values in Python?
- The principle of python decorator
- Python dictionary usage summary
- How to install python, configure environment variables, and change sources for third-party libraries
- [Conda] python data analysis/deep learning environment configuration windows+conda+jupyter+pytorch
- 【Conda】python environment setup , windows+conda+jupyter+pytorch (English Version)
- [Pandas] A primer on Pandas processing csv file datasets (neural network/machine learning algorithm data preprocessing)
- 100 days proficient in python (basic version) -- the first day: python and vscode environment installation
- How does python solve high concurrency
- Using the python library geopy method calculating the distance between the multiple sets of longitude and latitude
- JavaScript, Python 8x, 29x slower than C++?
- python---SSH connection to linux service
- [reprint] Python - list comprehension
- Python Computer Vision Programming - Chapter 2 Local Image Descriptors
- "Compared to Excel, easy learning Python data analysis," reading notes -- -- -- -- -- - data operation
- Why is a function in the math module opened in python or in the IDE of pycharm, only the definition is not implemented?