本文共 2330 字，大约阅读时间需要 7 分钟。

1. 题目

给定一个只包含正整数的非空数组。

注意:

示例 1:输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2:输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/partition-equal-subset-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

• 每个元素取或者不取，动态规划，求解所有可能的和情况

class Solution {
   public:    bool canPartition(vector
   
    & nums) {
       	if(nums.size() <= 1)    		return false;    	int sum = 0, i, j;    	for(i = 0 ; i < nums.size(); ++i)    		sum += nums[i];    	if(sum&1)	return false;//奇数不可分    	//dp求解，每个元素拿或者不拿，求解所有的状态    	set
    
      state;    	state.insert(0);//初始化    	state.insert(nums[0]);    	for(i = 1; i < nums.size(); ++i)    	{
       		for(auto it = state.rbegin(); it != state.rend(); ++it)    		{
   	//用set，不能用哈希set，且必须逆序遍历，新插入的不会被本次遍历到    			state.insert(*it+nums[i]);    		}    		if(state.count(sum>>1))    			return true;    	}    	return false;    }};
    
   

936 ms 16.3 MB

• 采用数组实现dp

class Solution {
   public:    bool canPartition(vector
   
    & nums) {
       	if(nums.size() <= 1)    		return false;    	int sum = 0, i, j;    	for(i = 0 ; i < nums.size(); ++i)    		sum += nums[i];    	if(sum&1)	return false;//奇数不可分    	//dp求解，每个元素拿或者不拿，求解所有的状态    	vector
    
      state(sum+1, false);    	state[0] = true;//初始化    	state[nums[0]] = true;    	for(i = 1; i < nums.size(); ++i)    	{
       		for(j = sum; j >= 0; --j)    		{
   	                if(state[j])    			    state[j+nums[i]] = true;    		}    		if(state[sum>>1])    			return true;    	}    	return false;    }};
    
   

312 ms 8.9 MB

• 再优化下存储空间，只查找到 sum/2 的状态，超过的忽略
• 以下代码有bug [99,1] 这个例子，第一个数会越界

class Solution {
   public:    bool canPartition(vector
   
    & nums) {
       	if(nums.size() <= 1)    		return false;    	int sum = 0, i, j;    	for(i = 0 ; i < nums.size(); ++i)    		sum += nums[i];    	if(sum&1)	return false;//奇数不可分    	//dp求解，每个元素拿或者不拿，求解所有的状态        sum >>= 1;    	vector
    
      state(sum+1, false);    	state[0] = true;//初始化    	state[nums[0]] = true;    	for(i = 1; i < nums.size(); ++i)    	{
       		for(j = sum; j >= 0; --j)    		{
   	                if(state[j] && j+nums[i] <= sum)    			    state[j+nums[i]] = true;    		}    		if(state[sum])    			return true;    	}    	return false;    }};
    
   

164 ms 8.8 MB

转载地址：https://michael.blog.csdn.net/article/details/106216416 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！