377. 组合总和 IV

组合总和 IV

• 难度: medium
• 原始链接: https://leetcode.cn/problems/combination-sum-iv
• 标签: 动态规划

解法一: 递归, 记忆化搜索

go

func combinationSum4(nums []int, target int) int {
  record := make([]int, target+1)
  for i := 1; i <= target; i++ {
    record[i] = -1
  }
  var dfs func(cur int) int
  dfs = func(cur int) int {
    if cur == 0 {
      return 1
    } else if record[cur] > -1 {
      return record[cur]
    }
    sum := 0
    for _, num := range nums {
      if cur >= num {
        sum += dfs(cur - num)
      }
    }
    record[cur] = sum
    return sum
  }
  return dfs(target)
}

解法二: 迭代

go

func combinationSum4(nums []int, target int) int {
  record := make([]int, target+1)
  record[0] = 1
  for i := 1; i <= target; i++ {
    sum := 0
    for _, num := range nums {
      if i >= num {
        sum += record[i-num]
      }
    }
    record[i] = sum
  }
  return record[target]
}