Difficulty: Medium

Related Topics: Dynamic Programming

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:

  1. Input: nums = [1,5,11,5]
  2. Output: true
  3. 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.

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

Solution

Language: Java

class Solution {
    private Boolean[][] memo;

    // 可以把这个问题看成 0/1背包 问题，问你如何在 nums 数组里面挑选数字
    // 可以使得它的和等于 sum(nums) / 2
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;

        // 奇数无法完全分割，无解
        if ((sum & 1) == 1) return false;

        int volume = sum >> 1;

        memo = new Boolean[nums.length][volume + 1];

        return dp(nums, 0, volume);
    }

    private boolean dp(int[] nums, int i, int volume) {
        // 出口
        // 1. 非法参数
        if (i >= nums.length || volume < 0) return false;
        // 2. 唯一解
        if (volume == 0) return true;
        // 3. 记忆
        if (memo[i][volume] == null) return false;

        // 做选择
        // 1. 不选择当前数字
        // 2. 选择当前数字，背包容量 - 当前数字大小
        return memo[i][volume] = dp(nums, i + 1, volume) || 
                                 dp(nums, i + 1, volume - nums[i]);
    }
}