LeetCode 416. Partition Equal Subset Sum

[Woodyiiiiiii]

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

---

一开始我打算用DFS+回溯法来做，遍历所有的子集，得到结果：

// dfs + backtracking 不能通过OJ，Time Limit Exceed
class Solution {
    boolean res = false;
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        dfs(nums, sum, 0, 0);
        return res;
    }
    public void dfs(int[] nums, int sum, int preSum, int i) {
        if (preSum == sum - preSum) {
            res = true;
            return;
        }else if (preSum > sum - preSum) {
            return;
        }
        for (int j = i; j < nums.length; ++j) {
            dfs(nums, sum, preSum + nums[j], j + 1);
        }
    }
}

或者是获取所有subSet子集：

class Solution {
    public boolean canPartition(int[] nums) {
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        List<Integer> dp = new ArrayList<>();
        
        for (int num : nums) {
            dp.add(0);
            int size = dp.size();
            for (int i = 0; i < size; ++i) {
                int subSum = dp.get(i);
                subSum += num;
                if (subSum * 2 == sum) {
                    return true;
                }
                dp.add(subSum);
            }
        }
        
        return false;
        
    }
}

结果都是TLE，所以要进行优化。

想到要用到动态规划DP方法，首先得到数组内所有数值的累加和sum，如果sum是奇数则直接返回false，否则令target等于sum/2，接下来问题是找到子集的和为target；创建boolean类型的一维DP数组dp，长度为target+1，dp[0]初始化为true，遍历数组，对每个数num，从target开始递减遍历到num，状态转移方程是dp[i] = dp[i] || dp[i - num]，就相当于判断之前i-num进一步加上num后等于i值。

注意： 要从target从后往前遍历是因为防止num=1时，因为dp[0]初始化为true，导致dp数组内所有值为true；这实际上是一个背包问题，跟硬币coin change相似，都是以结果值作为dp数组长度，从背包中取出数值凑成条件；但coin change因为每次都可以选择多个硬币，所以是从左到右、且内循环才是硬币数值，但此题是只能选一种，所以外循环才是数组元素，并且是从右到左遍历。

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

---

参考资料：

• https://leetcode.com/problems/partition-equal-subset-sum/
• [LeetCode] 416. Partition Equal Subset Sum grandyang/leetcode#416