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

leetcode 377. Combination Sum IV (python)

2022-08-06 11:54:04big 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
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


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.

Random recommended