题目描述

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

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

    来源，leetcode 每日一题 416. 分割等和子集

例如：

  1. 输入: [1, 5, 11, 5]
  3. 输出: true
  5. 解释: 数组可以分割成 [1, 5, 5] 和 [11].

解题思路

  1. 当数组的元素和为奇数的时候，那么它肯定不能等分，排除
  2. 当数组的元素最大值>416. 分割等和子集 - 图1的时候，意味着，除了最大值以外，其他所有元素和加起来要小于总和的一半，显然也不可能，排除
  3. 其余情况，则是很常见的dp思路

    dp，每个位置对于值j 可以有两个选择，选或者不选。 如果选，那么这个位置的结果是什么？ result[i][j] = result[i-1][j-nums[i]] ->这个的解释： j = (j-nums[i]) + nums[i] 当前位置成立的前提条件是，j-nums[i]要成立。 如果不选，这个位置的结果是什么？（当此处的值>j的时候是一定不选的） result[i][j] = result[i-1][j]
    依次类推，当j == target的时候，就是结果

代码

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.         int sum = 0;
  5.         int n = nums.size();
  6.         if (n < 2) {
  7.             return false;
  8.         }
  9.         int maxNum = 0;
  10.         for (int i = 0; i < n; i++) {
  11.             sum += nums[i];
  12.             maxNum = (maxNum >= nums[i] ? maxNum : nums[i]);
  13.         }
  14.         if (sum % 2 != 0) {
  15.             return false;
  16.         }
  17.         int target = sum / 2;
  18.         if (maxNum > target) {
  19.             return false;
  20.         }
  21.         vector<vector<int>> result(n+1, vector<int>(target+1, 0));
  22.         for (int i = 0; i < n; i++) {
  23.             result[i][0] = true; 
  24.         }
  25.         result[0][nums[0]] = true;
  26.         for (int i = 1; i < n; i++) {
  27.             for (int j = 1; j < target + 1; j++) {
  28.                 if (j > nums[i]) {
  29.                     result[i][j] = result[i-1][j] | result[i-1][j-nums[i]];
  30.                 } else {
  31.                     result[i][j] = result[i-1][j];
  32.                 }
  33.             }
  34.         }
  35.         return result[n-1][target];
  36.     }
  38. };