问题

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

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

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

思路

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等
那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了

01背包问题

背包问题，大家都知道，有N件物品和一个最多能被重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大

背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等

要注意题目描述中商品是不是可以重复放入

即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的

要明确本题中我们要使用的是01背包，因为元素我们只能用一次

回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集
那么来一一对应一下本题，看看背包问题如果来解决

只有确定了如下四点，才能把01背包问题套到本题上来

  • 背包的体积为sum / 2
  • 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
  • 背包如何正好装满，说明找到了总和为 sum / 2 的子集
  • 背包中每一个元素是不可重复放入

以上分析完，我们就可以套用01背包，来解决这个问题了

  • 确定dp数组以及下标的含义

    • dp[i]表示背包总容量是i，最大可以凑成i的子集总和为dp[i]

  • 确定递推公式

    • 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    • 本题，物品i的重量是nums[i]，其价值也是nums[i]
    • 所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  • dp数组如何初始化

    1. // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
    2. // 那么背包内总和不会大于20000，所以定义一个20000大的数组。
    3. int[] dp = new int[20001];

  • 确定遍历顺序

    • 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒叙遍历！
      1. for(int i = 0; i < nums.length; i++) {
      2. for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
      3.    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
      4. }
      5. }

  • 举例推导dp数组

    • dp[i]的数值一定是小于等于i的，如果**dp[i] == i**说明，集合中的子集总和正好可以凑成总和**i**，理解这一点很重要

640 (1).png
最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int sum = 0;
  5.         // dp[i]中的i表示背包内总和
  6.         // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
  8.         int[] dp = new int[20001]; 
  10.         for (int i = 0; i < nums.length; i++) {
  11.             sum += nums[i];
  12.         }
  13.         if (sum % 2 == 1) 
  14.             return false;
  16.         int target = sum / 2;
  18.         // 开始 01背包 
  19.         for(int i = 0; i < nums.length; i++) {
  20.             // 每一个元素一定是不可重复放入，所以从大到小遍历
  21.             for(int j = target; j >= nums[i]; j--) { 
  22.                 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
  23.             }
  24.         }
  25.         // 集合中的元素正好可以凑成总和target 
  26.         if (dp[target] == target) 
  27.             return true;
  28.         return false;      
  29.     }
  30. }
  • 时间复杂度：leetcode-416：分割等和子集 - 图2
  • 空间复杂度：leetcode-416：分割等和子集 - 图3，虽然dp数组大小为一个常数，但是大常数