LeetCode 416. 分割等和子集（动态规划）数据结构与算法Michael是个半路程序员-

1. 题目

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

注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 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<int>& 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<int> 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<int>& 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<bool> 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 的状态，超过的忽略

class Solution { public: bool canPartition(vector<int>& 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<bool> 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