MediumNo. 0377

Combination Sum IV — LeetCode 377 Python Solution

Topics
Array, Dynamic Programming
On a study list
Blind 75
Reading time
2 min

The 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 test cases are generated so that the answer can fit in a 32-bit integer.

Example

Input
nums = [1,2,3], target = 4
Output
7
Explanation
The possible combination ways are:

Python solution

PythonSolution
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        f = [1] + [0] * target
        for i in range(1, target + 1):
            for x in nums:
                if i >= x:
                    f[i] += f[i - x]
        return f[target]

Complexity

Time
O(n × target)
Space · auxiliary
O(target)where n is the length of the array

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 377. Combination Sum IV is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0039Combination SumMedium
0376Wiggle SubsequenceMedium
0368Largest Divisible SubsetMedium
0045Jump Game IIMedium
0053Maximum SubarrayMedium
0055Jump GameMedium

Frequently asked questions

How hard is LeetCode 377. Combination Sum IV?

LeetCode 377. Combination Sum IV is rated Medium on LeetCode.

What is the time complexity of LeetCode 377. Combination Sum IV?

The Python solution on this page runs in O(n × target).

What is the space complexity of LeetCode 377. Combination Sum IV?

The Python solution on this page uses O(target), where n is the length of the array auxiliary space.

What topics does LeetCode 377. Combination Sum IV cover?

LeetCode 377. Combination Sum IV is tagged Array and Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.