题目描述

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

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

题目分析

题目中隐含了一个信息，“两个子集的元素和相等”，意味着每个子集都是 sum/2。
问题可以转化为，使用数组内的元素相加，是否可以组成 sum/2.（有一个组合成功，剩余值必然就是另一个 sum/2）。
想象一个容器用于存储所有可能的相加结果，每次枚举数组元素时，需要与容器内存在的结果相加，然后重新放入容器。
以 [1,5,11,5] 为例：
– 第1个元素 1，容器 [1]
– 第2个元素 5，容器 [1, 5, 6]
– 第3个元素 11，容器 [1, 5, 6, 11, 12, 16, 17]

可以使用 dp[i] 表示是否有和为 i 的结果，然后进行递推dp[i] = dp[i] || dp[i - 数组元素]

时间复杂度 O(m * n)，其中 m 是 sum/2，n 是元素个数

Java

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    if (sum % 2 == 1) {
        return false;
    }
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int n : nums) {
        for (int j = target; j >= n; j--) {
            dp[j] = dp[j] || dp[j - n];
        }
        if (dp[target]) {
            return true;
        }
    }
    return false;
}

Kotlin

fun canPartition(nums: IntArray): Boolean {
    val sum = nums.sum()
    if (sum % 2 == 1) {
        return false
    }
    val target = sum / 2
    val dp = BooleanArray(target + 1)
    dp[0] = true
    for (n in nums) {
        for (j in target downTo n) {
            dp[j] = dp[j] || dp[j - n]
        }
        if (dp[target]) {
            return true
        }
    }
    return false
}