2022-02-04：组合总和 Ⅳ。 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target

2022-02-04：组合总和 Ⅳ。 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 示例 1： 输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。 提示： 1 <= nums.length <= 200 1 <= nums[i] <= 1000 nums 中的所有元素 互不相同 1 <= target <= 1000 力扣377。

答案2022-02-04：

自然智慧即可。递归。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    nums := []int{1, 2, 3}
    target := 4
    ret := combinationSum42(nums, target)
    fmt.Println(ret)
}

// 当前剩下的值是rest，
// nums中所有的值，都可能作为分解rest的，第一块！全试一试
// nums, 无重复，都是正
// rest,
func ways(rest int, nums []int) int {
    if rest < 0 {
        return 0
    }
    if rest == 0 {
        return 1
    }
    ways0 := 0
    for _, num := range nums {
        ways0 += ways(rest-num, nums)
    }
    return ways0
}

var dp = make([]int, 1001)

func combinationSum41(nums []int, target int) int {
    //Arrays.fill(dp, 0, target + 1, -1);
    for i := 0; i < target+1; i++ {
        dp[i] = -1
    }
    return process1(nums, target)
}

func process1(nums []int, rest int) int {
    if rest < 0 {
        return 0
    }
    if dp[rest] != -1 {
        return dp[rest]
    }
    ans := 0
    if rest == 0 {
        ans = 1
    } else {
        for _, num := range nums {
            ans += process1(nums, rest-num)
        }
    }
    dp[rest] = ans
    return ans
}

// 剪枝 + 严格位置依赖的动态规划
func combinationSum42(nums []int, target int) int {
    //Arrays.sort(nums);
    sort.Ints(nums)
    //int[] dp = new int[target + 1];
    dp := make([]int, target+1)
    dp[0] = 1
    for rest := 1; rest <= target; rest++ {
        for i := 0; i < len(nums) && nums[i] <= rest; i++ {
            dp[rest] += dp[rest-nums[i]]
        }
    }
    return dp[target]
}

执行结果如下：

左神java代码