摘要：今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号算法精选里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目难度: 中等
原题链接[1]
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~
给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
输入：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)请注意，顺序不同的序列被视作不同的组合。示例 2：分析题目, 可以发现它跟上道题目Leetcode 剑指 Offer II 103.零钱兑换非常类似, 只是把求最少数字个数改成了求有效组合数所以我们可以同样利用动态规划的思路, 只需要稍作改动, 具体做法如下:定义 dp[t] 代表总和为 t 的有效组合数, 显然 t 的取值范围是[0,target], 而初始情况是 dp[0]=1, 代表空集时的有效组合数为 1, 其他 dp 值为 0由于顺序不同的序列被视作不同的组合, 所以即使组合总和相同, 只要其最后一个数字不同, 就是不同的组合我们可以利用这一点, 外层循环遍历所有可能的组合总和 sm, 即从 1 到 target, 然后内层循环遍历数组的每个数字 num, 作为当前组合的最后一个数字, 只要它不超过当前组合总和, 就可以将dp[t-num]的值累加到当前dp[t]用数学公式来表示, 就是 dp[t]=sum(dp[t-num]) (num in nums && num 最终遍历完成后的 dp[target] 即为所求接下来我们来思考进阶问题: 数组包含负数的情况此时总是可以构造出总和为 0 的数字组合, 例如正数 a 和负数-b, 我们可以使用 b 个 a 和 a 个 -b 形成组合, 其总和就是 0这样有效组合数就会变得无限了, 因为总是可以加上任意个 0, 总和仍保持不变所以当数组存在负数时, 需要额外加上对有效组合长度的限制, 否则总是可以无限扩展下面的代码有详细的注释, 方便大家理解class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:# dp[t]存储总和为t的有效组合个数dp = [0] * (target + 1)# 初始化dp[0]为1, 即空集dp[0] = 1for t in range(1, target + 1):for num in nums:if t >= num:# 当前dp[t]可以从dp[t-num]转移而来, 即最后一个元素使用numdp[t] += dp[t - num]# 最终结果就是dp[target]return dp[target]大家可以在下面这些地方找到我~
我的 GitHub[2]
我的 Leetcode[3]
我的 CSDN[4]
我的知乎专栏[5]
我的头条号[6]
我的牛客网博客[7]
, 欢迎大家扫码关注~
[1]
原题链接:
[2]
我的 GitHub:
[3]
我的 Leetcode:
[4]
我的 CSDN:
[5]
我的知乎专栏:
[6]
[7]
我的牛客网博客:
来源：王老师高考咨询
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!