416. 分割等和子集

leetcode 416. 分割等和子集

题目：416. 分割等和子集

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

注意:

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

示例1:

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

示例2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.输入的字符串只含有小写英文字符。

方法：动态规划

思路：动态规划。状态转移方程为：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])。dp[j]表示剩余空间为j时所能装下的最体积。把nums中的数字看作体积。将是否可以将这个数组分割成两个子集，使得两个子集的元素和相等这个问题转换成是否能从使数组中的选择一些元素，使得这些元素的和刚好为数组所有元素总和的一半。然后将其装换成01背包问题，判断当背包空间为数组所有元素总和的一半时，所装入的体积最大是否等于背包空间，如果相等则说明可以从使数组中的选择一些元素，使得这些元素的和刚好为数组所有元素总和的一半，即说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

运行数据：执行用时：18 ms，内存消耗：38.9 MB

复杂度分析：

• 时间复杂度：O(n * halfSum)，n为nums的长度，halfSum为nums的和的一半。
• 空间复杂度：O(halfSum)，halfSum为nums的和的一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// LeetCode指定调用方法 
public boolean canPartition(int[] nums) {
    int n = nums.length;
    if (n == 1) {
        return false;
    }

    int sum = 0;
    for (int i : nums) {
        sum += i;
    }

    if (sum % 2 != 0) {
        return false;
    }

    int halfSum = sum >> 1;

    int[] dp = new int[halfSum + 1];

    for (int i = 0; i < n; i++) {
        for (int j = halfSum; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[halfSum] == halfSum;
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！