377.组合总和Ⅳ

链接：377.组合总和Ⅳ
难度：Medium
标签：数组、动态规划
简介：给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题解 1 - python

• 编辑时间：2024-04-23
• 执行用时：37ms
• 内存消耗：16.5MB
• 编程语言：python
• 解法介绍：dp[i]表示i为target时的最大次数。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        dp = [0 for _ in range(target + 1)]
        dp[0] = 1
        for cur_target in range(1, target + 1):
            for num in nums:
                if num > cur_target: break
                dp[cur_target] += dp[cur_target - num]
        return dp[target]

题解 2 - typescript

• 编辑时间：2021-04-24
• 执行用时：104ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：动态规划。

function combinationSum4(nums: number[], target: number): number {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= target; i++) {
    for (const num of nums) {
      if (i >= num) {
        dp[i] += dp[i - num];
      }
    }
  }
  return dp[target];
}

题解 3 - javascript

• 编辑时间：2021-09-14
• 执行用时：84ms
• 内存消耗：40MB
• 编程语言：javascript
• 解法介绍：动态规划。

function combinationSum4(nums: number[], target: number): number {
  nums.sort((a, b) => a - b);
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= target; i++) {
    for (const num of nums) {
      if (i < num) break;
      dp[i] += dp[i - num];
    }
  }
  return dp[target];
}

题解 4 - python

• 编辑时间：2024-04-22
• 执行用时：44ms
• 内存消耗：16.5MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        @cache
        def dfs(target: int) -> int:
            if target == 0: return 1
            res = 0
            for num in nums:
                if num > target: break
                res += dfs(target - num)
            return res
        return dfs(target)