LEETCODE 416. Partition Equal Subset Sum解题思路分析

题目大意：

分割等和子集

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

注意:

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

示例 1:

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

示例 2:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=416

解题思路分析：

虽然这是一道中等难度的题目，但我还是想了一会才解出来。话说开始并没有意识到要用dp去求解，动态规划的题目果然是很烧脑，我们需要锻炼着发现规律。

回到本题，题目要求将一个数组的数分成两部分，并保证这两部分的和相同。这个条件很容易想到，既然两边和相同，那个这个和一定是该数组所有数的和除以2。接下来考虑，如果总和不能够被2整除的话，那么一定不会存在解，直接返回false即可。另外还有一种极端情况，即数组长度为0或者1的时候，我们也无法分割，故而也可直接返回false。

我们算出数组总和为sum，分割后每个子集的和应为sum/2，我们称之为target。这时，我们问题就转化为，我们能否在数组中找到n个数，并且他们的和为target。暴力解这个问题肯定会超时，因此我们需要使用动态规划或者说是记忆数组来优化问题。定义一个boolean型数组dp[]，dp[i]表示，数组中是否存在n个数字的和为i。初始化dp[0]=true。也就是说我们可以找到和为0的n个数（此时n为0）。

那么如何求解dp[i]呢？这里我们需要使用两层循环，第一层循环数组中所有的数字num，第二层则是循环从0到target的值，也就是dp数组的下标。当dp数组当前下标i对应的值为true时，说明我们可以从数组中找到一些数字，并且他们的和为i。那么，这个i再加上当前遍历到的数字num，也是能够组成的一个和，即dp[i+num]也为true。

这2层循环的目的实际上就是将所有数字能够组成的和都遍历了一遍，利用他们的和作为下标，存储在dp数组中，因此dp数组中所有为true的下标，都是我们可以组成的和，最终结果返回下标为target的值即可。

看下完整代码：

public boolean canPartition(int[] nums) {
    // 如果数组长度小于2，无法分割成两个子集合
    if (nums.length < 2) {
        return false;
    }
    // 计算出数组中所有数的和。
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    // 如果总和不能被2整除，返回false。
    if (sum % 2 != 0) {
        return false;
    }
    // target为每个集合的和。
    int target = sum / 2;
    // dp[i]表示是否可以从nums中找出一些数字，并且和为i。
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    // 遍历每个数字
    for (int num : nums) {
        // 遍历出加上每个数字可以组成的和。
        // 如果加上该数字num超出target范围，是无效解，可以忽略。
        // 因此此处for语句的起始条件为i = target - num
        for (int i = target - num; i >= 0; i--) {
            // 如果i是合法的和，那么i加上当前num可以组成一个新的和
            if (dp[i]) {
                // 将dp[i + num]设置为true
                dp[i + num] = true;
                // 如果已经计算出target为true，直接返回
                if (dp[target]) {
                    return true;
                }
            }
        }
    }
    // 返回target的值。
    return dp[target];
}

本题平均用时4ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-416-partition-equal-subset-sum解题思路分析/