题目主要信息

给定一个只包含正整数的数组 nums ，请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。

总结：其实就是判断数组中是否存在一些元素的和等于总元素和sum的一半。

方法一：动态规划

具体方法

首先求出所有元素的和sum，

• 如果sum为奇数，直接返回false。
• 如果元素中最大的数大于sum的一半，直接返回false。

设置dp二维数组dp[i] [j] 表示从0-i位置的元素中是否存在和是否为j的情况

下面给出dp的动态转移方程为

• $dp[i][j]=dp[i][j]\mathrm{\mid }dp[i-1][j-nums[i]]j>nums[i]dp[i]\; [j]\; =\; dp[i]\; [j]\; |\; dp[i-1]\; [j\; -\; nums[i]]\; j>nums[i]$

最后直接返回$dp[len-1][sum\mathrm{/}2]dp[len-1]\; [sum/2]$

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean partition (int[] nums) {
        // write code here
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        // 求sum和最大值
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        // 和为奇数
        if (sum % 2 != 0) {
            return false;
        }
        // 最大值大于sum的一半
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        // 初始化
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        // dp数组更新
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // 返回最终结果
        return dp[n - 1][target];
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\ast sum\mathrm{）}O（n*sum）$，两层循环
• 空间复杂度：$O\mathrm{（}n\ast sum\mathrm{）}O（n*sum）$，辅助二维数组dp

方法二：空间优化

具体方法

可以发现在上面计算 dp 的过程中，每一行的 dp 值都只与上一行的 dp 值有关，因此只需要一个一维数组即可将空间复杂度降到O(target)。此时的转移方程为：

$dp[j]=dp[j]\mathrm{\mid }dp[j-nums[i]]dp[j]\; =\; dp[j]\; |\; dp[j-nums[i]]$

且需要注意的是第二层的循环我们需要从大到小计算，因为如果从小到大更新 dp 值，那么在计算dp[j] 值的时候，dp[j−nums[i]] 已经是被更新过的状态，不再是上一行的dp 值。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean partition (int[] nums) {
        // write code here
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        // 求sum和最大值
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        // 和为奇数
        if (sum % 2 != 0) {
            return false;
        }
        // 最大值大于sum的一半
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        // 一维dp数组
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\ast sum\mathrm{）}O（n*sum）$，两层循环
• 空间复杂度：$O\mathrm{（}sum\mathrm{）}O（sum）$，辅助一维数组dp