2022-02-04：组合总和 Ⅳ。 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 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 mainimport ("fmt""sort"
)func main() {nums := []int{1, 2, 3}target := 4ret := 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 := 0for _, 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 := 0if rest == 0 {ans = 1} else {for _, num := range nums {ans += process1(nums, rest-num)}}dp[rest] = ansreturn 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] = 1for 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代码

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！