416. 分割等和子集——【Leetcode每日刷题】

喜欢ヅ旅行 2024-03-25 09:57 14阅读 0赞

### 416. 分割等和子集 ###

给你一个 **只包含正整数** 的 **非空** 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

##### 示例 1： #####

> 输入：nums = \[1,5,11,5\]  
> 输出：true  
> 解释：数组可以分割成 \[1, 5, 5\] 和 \[11\] 。

##### 示例 2： #####

> 输入：nums = \[1,2,3,5\]  
> 输出：false  
> 解释：数组不能分割成两个元素和相等的子集。

##### 提示： #####

*  1 <= nums.length <= 200
 *  1 <= nums\[i\] <= 100

#### 思路：(动态规划) ####

[0-1背包问题][0-1]

先求数组数组nums 中所有数之和sum：

*  和为奇数时，一定不能分割成两个和相等的子集，返回 false;
 *  和为偶数时，则有可能分割成两个和相等的子集，需进一步判断，此时可理解为，能否找到和为sum/2 的子集，从而可转换成0-1背包问题；

**设置状态：**

*  dp\[i\]\[j\] 表示考虑下标\[0, i\] 这个区间里的所有整数，在他们当中是否能够选出一些数，使得这些数之和恰好为整数 j

**状态转移方程：**

*  不选nums\[i\] : dp\[i\]\[j\] = dp\[i -1\]\[j\];
 *  选择nums\[i\]:
    
     *  nums\[i\] == j, dp\[i\]\[j\] = true;
     *  nums\[i\] < j, dp\[i\]\[j\] = dp\[i -1\]\[j - nums\[i\]\];

**举个栗子：**

![在这里插入图片描述][8d6c5e85e69e4717bba82b11a8b74a5e.jpeg]

#### 代码： ####

**Java**

**二维dp数组**

public class CanPartition {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int[] nums = {
        1,5,11,5};
    		System.out.println(canPartition(nums));
    	}
    	public static boolean canPartition(int[] nums) {
        
    		int sum  = 0;
    		for(int i = 0; i < nums.length; i++) {
        
    			sum += nums[i];
    		}
    		if(sum % 2 != 0) {
        
    			return false;
    		}
    		boolean[][] dp = new boolean[nums.length][sum/2 + 1];
    		dp[0][0] = true;
    		if(nums[0] <= sum/2) {
        
    			dp[0][nums[0]] = true;
    		}
    		for(int i = 1; i < nums.length; i++) {
        
    			for(int j = 1; j <= sum/2; j++) {
        
    				dp[i][j] = dp[i - 1][j];
    				
    				if(nums[i] <= j) {
        
    					dp[i][j] |= dp[i - 1][j - nums[i]];
    				}
    				if(dp[i][sum/2]) {
        
    					return true;
    				}
    			}
    		}
    		return false;
        }
    }

**优化为一维dp数组：**

public class CanPartition {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int[] nums = {
        1,5,11,5};
    		System.out.println(canPartition(nums));
    	}
    	public static boolean canPartition(int[] nums) {
        
    		int sum  = 0;
    		for(int i = 0; i < nums.length; i++) {
        
    			sum += nums[i];
    		}
    		if(sum % 2 != 0) {
        
    			return false;
    		}
    		boolean[] dp = new boolean[sum/2 + 1];
    		dp[0] = true;
    		for(int i = 1; i <= nums.length; i++) {
        
    			for(int j = sum/2; j >= nums[i - 1]; j--) {
        
    				dp[j] |= dp[j - nums[i - 1]];
    			}
                if(dp[sum/2])
    				return true;
    		}
    		return false;
        }
    }

**C++**

class Solution {
        
    public:
        bool canPartition(vector<int>& nums) {
        
            int sum = 0;
            for(int num : nums){
        
                sum += num;
            }
            if(sum % 2 != 0) return false;
            sum /= 2;
            vector<int> dp(sum + 1);
            dp[0] = 1;
            for(int i = 1; i <= nums.size(); i++){
        
                for(int j = sum; j >= nums[i - 1]; j--){
        
                    dp[j] |= dp[j - nums[i - 1]];
                }
            }
            return dp[sum];
        }
    };

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

![在这里插入图片描述][60737da6cda94874b0f88867d6e26270.png]  
力扣运行结果：  
![在这里插入图片描述][800aaf21199c4a20accb1986e1c894df.png]

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

*  **时间复杂度**： O ( n ∗ t a r g e t ) ) O(n\*target)) O(n∗target))，其中 n 是数组的长度，target 是整个数组的元素和的一半。需要计算出所有的状态，每个状态在进行转移时的时间复杂度为 O(1)。
 *  **空间复杂度**： O ( t a r g e t ) ) O(target)) O(target))，其中 targe 是整个数组的元素和的一半。空间复杂度取决于 dp 数组，在不进行空间优化的情况下，空间复杂度是  O ( n ∗ t a r g e t ) ) O(n\*target)) O(n∗target))，在进行空间优化的情况下，空间复杂度可以降到  O ( t a r g e t ) ) O(target)) O(target))。

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

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

[0-1]: https://blog.csdn.net/weixin_43412762/article/details/129485663
[8d6c5e85e69e4717bba82b11a8b74a5e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ee432fc725ba4fea919a58cb75527530.png
[60737da6cda94874b0f88867d6e26270.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d385d4de9dd54fddba23d638a4fb905c.png
[800aaf21199c4a20accb1986e1c894df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ec80109f489f4eee95838175dbca0b7c.png
[Link 1]: https://leetcode.cn/problems/partition-equal-subset-sum/description/