电商平台规则,网站建设专家推荐乐云seo,WordPress5.1后台常规没有备案,网站建设托管pfthost给你一个由 不同 整数组成的数组 nums #xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。 示例 1#xff1a;
输入#xff1a;nums [1,2,3], target 4
输出#xff1a;7
解释#…给你一个由 不同 整数组成的数组 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)
请注意顺序不同的序列被视作不同的组合。示例 2
输入nums [9], target 3
输出0提示
1 nums.length 2001 nums[i] 1000nums 中的所有元素 互不相同1 target 1000
class Solution {
public:int combinationSum4(vectorint nums, int target) {//相对于 回溯做此题dp更快回溯超时//每个物品能拿n次(正序)----------- 完全背包// 1、允许 元素相同顺序不同的结果 。所以是先遍历背包//dp[j]:容量为j的背包装满 组合为dp[j]种//假如已经有 1 那么装满dp[5]有dp[4]种方法// 2 dp[3]//.............................// 5 dp[0]vectorintdp(target1,0); //需要累加所以得赋值为0dp[0] 1;for(int i 0;i target;i){for(int j 0;j nums.size();j){//dp[i] dp[i - nums[j]] INT32_MAX。还不能写成加法怕超限if(i nums[j] dp[i] INT32_MAX - dp[i - nums[j]]) dp[i] dp[i - nums[j]];}}return dp[target];}
};
