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

原题链接

leetcode.com/problems/co…

您的支持是我最大的动力

copyright notice
author[big wang],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/218/202208061137300699.html

Random recommended