377. 组合总和 Ⅳ ——【Leetcode每日一题】

分手后的思念是犯贱 2024-03-25 20:00 20阅读 0赞

### 377. 组合总和 Ⅳ ###

给你一个由 **不同** 整数组成的数组 `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 <= 200
 *  1 <= nums\[i\] <= 1000
 *  nums 中的所有元素 **互不相同**
 *  1 <= target <= 1000

**进阶：** 如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

#### 思路：(动态规划、完全背包) ####

数组nums中的整数使用次数的限制，此问题属于 0-1背包 的 **完全背包** ，解法和 **0-1背包** 类似：

[0 - 1背包问题（万能统一代码）][0 - 1]

**该问题求元素组合数，是带顺序的，也就是说整数必须按一定的顺序放入背包**：

*  求解 **顺序的完全背包** 问题时，对 **物品的迭代** 应该 放在最里层，对 **背包的迭代** 放在外层，只有这样才能让物品 **按一定顺序** 放入背包中。
 *  定义 `dp` 数组：`dp[i]` 表示 总和为 `i` 的元素组合数；
 *  状态转移方程为：
    
     *  初始状态：  
         d p \[ 0 \] = 1 dp\[0\] = 1 dp\[0\]=1
     *  如果 `nums[j]` <= `i` 时，加上 `nums[j]` 的组合数等于 不加 `nums[j]` 的组合数：  
         d p \[ i \] + = d p \[ i − n u m s \[ j \] \] dp\[i\] += dp\[i - nums\[j\]\] dp\[i\]\+=dp\[i−nums\[j\]\]

#### 代码：(Java / C++) ####

**java**

public class CombinationSum4 {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int[] nums = {
        1, 2, 3};
    		int target = 4;
    		System.out.println(combinationSum4(nums, target));
    	}
    	public static int combinationSum4(int[] nums, int target) {
        
    		
    		//排列带顺序，求解有顺序的完全背包时，对物品的的迭代放里面，对背包的迭代放外面
    		//只有这样才能让物品按一定顺序放入背包
    		int[] dp = new int[target + 1];
    		for(int i = 1; i <= target; i++) {
        
    			for(int num : nums) {
        
    				if(i == num ) {
        
    					dp[i]++;
    				}
    				if(i > num) {
        
    					dp[i] += dp[i - num];
    				}
    			}
    		}
    		
    		return dp[target];
        }
    }

**C++**

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    int combinationSum4(vector<int>& nums, int target) {
        
    
    	//排列带顺序，求解有顺序的完全背包时，对物品的的迭代放里面，对背包的迭代放外面
    	//只有这样才能让物品按一定顺序放入背包
    	vector<int> dp(target + 1, 0);
    	dp[0] = 1;
    	for (int i = 1; i <= target; i++) {
        
    		for (auto num : nums) {
        
    			if (i >= num) {
        
    				//c++计算的中间结果会溢出，但因为最终结果是int
    				//因此每次计算完都对INT_MAX取模，0LL是将计算结果提升到long long类型
    				dp[i] = (0LL + dp[i] + dp[i - num]) % INT_MAX;
    			}
    		}
    	}
    	return dp[target];
    }
    
    int main() {
        
    
    	vector<int> nums = {
        1, 2, 3};
    	int target = 4;
    
    	cout << combinationSum4(nums, target) << endl;
    
    	system("pause");
    	return 0;
    }

##### 运行结果： #####

![在这里插入图片描述][acf0671d204240cdb3d858d1cb07303f.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ∗ t a r g e t ) O(n \* target) O(n∗target) , target为 目标整数 `target`，len 为`nums`中整数的个数。
 *  **空间复杂度**： O ( t a r g e t ) O( target ) O(target) , target为 目标整数 `target`。

**有序完全背包相似题目：**

[139.单词拆分][139.]

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[0 - 1]: https://blog.csdn.net/weixin_43412762/article/details/129485663
[acf0671d204240cdb3d858d1cb07303f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/978a146b7c6b491f907128597f8e1f7e.png
[139.]: https://blog.csdn.net/weixin_43412762/article/details/129595558
[Link 1]: https://leetcode.cn/problems/combination-sum-iv/description/