[LeetCode]416.分割等和子集（C++）

1.代码

class Solution {
public:bool canPartition(vector<int>& nums) {int length = nums.size();int sumn = 0;int maxn = 0;for(int i = 0;i < length;i ++){sumn += nums[i];if(maxn < nums[i]) maxn = nums[i];}if(length < 2 || sumn % 2 == 1){return false;}int o = sumn / 2;if(maxn > o) return false;vector<vector<bool>> result(length,vector<bool>(o+1,false));for(int i = 0;i < length;i ++){result[i][0] = true;}result[0][nums[0]] = true;for(int i = 1;i < length;i ++){for(int j = 1;j <= o;j ++){if(j-nums[i]>=0){if(result[i-1][j-nums[i]] == true) result[i][j] = true;}if(result[i-1][j] == true) result[i][j] = true;}}return result[length-1][o];}
};

2.思路

如果数组长度小于2或存在一个大于总和一半的数或总和是奇数，那么就不存在等和子集。否则，构造一个矩阵记录前i个数中是否存在总和为j的子集。用了动态规划，如果result[i][j]为true，那么result[i-1][j]为true,或者result[i-1][j-nums[i]]为true。