【Leetcode】416.分割等和子集

416.分割等和子集

题目

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

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

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

方法（动态规划）

题目的意思我们可以换一种方式理解：假设数组nums的元素和为sum，是否能找到数组的一个子序列，使得它的和为sum/2。

在起初，我们可以先进行以下判断：

  • 如果nums的元素和sum为奇数，则不可能找到和为sum/2的子序列(因为nums中元素都为整数，和不可能为一个小数)，直接返回false。
  • 如果nums中最大的元素大于sum/2，也就意味着nums中其余所有元素的和小于sum/2，直接返回false。

    1.状态定义

    定义布尔类型的二维数组dp，dp[i][j]表示数组nums[0…i]中是否有和为j的子序列。

2.Base Case

base case为这个二维数组的第一行和第一列。

  • j=0时，无论i为多少，都为true。因为任何一个nums[0…i]都有一个和为0的子序列（子序列中元素为0）。所以，dp[i][0] = true
  • i = 0时，只能选择数组的第一个元素nums[0]，因此当j与nums[0]相等时为true，其余都为false。即，dp[0][nums[0]] = true

3.状态转换方程

当遍历到一个数nums[i]，我们有两种选择：选它或者不选它来构建和为j的子序列，这两种选择只要有一个为true，dp[i][j]就为true。

我们分为两种情况来讨论：

  • j >= nums[i]时：
    • 如果选nums[i]，那么只须判断nums[0…i-1]是否有和为j-nums[i]的子序列即可。即dp[i][j] = dp[i - 1][j - nums[i]]
    • 如果不选nums[i],则dp[i][j] = dp[i - 1][j]
  • j < nums[i]时：
    这种情况下不可以选nums[i]，因为一旦选nums[i]进子序列，由于nums[i] > j，子序列的和一定大于j，不可能等于j。因此dp[i][j]一定为false。因此dp[i][j] = dp[i - 1][j]

最后返回dp[n-1][target]即可，即nums数组中是否有和为target的子序列（target为sum/2)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean canPartition(int[] nums) {
    if(nums.length <= 1)
        return false;
    int sum = 0;
    for(int num : nums)
        sum += num;
    if(sum % 2 != 0)
        return false;
    int target = sum / 2;
    boolean[][] dp = new boolean[nums.length][target + 1];
    //设置base case
    for(int i = 0; i < n; i++)
        dp[i][0] = true;
    dp[0][nums] = true;
    for(int i = 1; i < nums.length; i++){
        for(int j = 1; j <= target; j++){
            if(j >= nums[i])
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
            else
                dp[i][j] = dp[i - 1][j]
        }
    }
    return dp[n - 1][target];
}

优化空间复杂度

在填充dp数组时我们发现，每一行的dp值都只与它上一行的dp值有关，因此我们可以优化掉行这个维度，只留列的维度。于是可以将dp数组由二维将为一维。

空间复杂度由O(n*target)降到O(target)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean canPartition(int[] nums) {
    if(nums.length <= 1)
        return false;
    int sum = 0;
    for(int num : nums)
        sum += num;
    if(sum % 2 != 0)
        return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    //设置base case
    dp[0] = true;
    for(int i = 0; i < nums.length; i++){
        //注意：这里要逆向填充
        //如果我们对于j从小到大更新dp值，在计算dp[j]的时候，dp[j - nums[i]]已经是该行被更新过的状态，而我们希望它是上一行的状态。
        for(int j = target; j >= num[i]; j--){
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
}