组合总和 Ⅳ。
给你一个由 不同 整数组成的数组 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。
自然智慧即可。递归。
代码用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]
}执行结果如下：
