416 Partition Equal Subset Sum

416. Partition Equal Subset Sum

1. Question

Given a non-empty array 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.

Note:

1. Each of the array element will not exceed 100.

2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

2. Implementation

(1) DP

思路: 如果nums可以被分成sum相等的两个subset，那么首先sum必须是偶数。接下来，我们要在nums数组里的n个数中，找到target sum/2是否存在，这是一个0/1背包问题。dp[i][j]表示nums里前i个数目中，是否存在sum是j。第一行代表没有任何数目，所以显然是false, 第一列代表target是0，这个表示空数组，任何数组都可以分成空数组和非空数组两部分，所以第一列初始化为true。接下来就是对于第i个数，如果它小于等于当前的sum j，只有两种操作: 选择i和不选择, 如果选择i的话，则dp[i][j] = dp[i - 1][j - nums[i]],不选择i的话，dp[i][j] = dp[i - 1][j].

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        int sum = 0;

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

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

        sum /= 2;
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][sum + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                if (i == 0) {
                    dp[i][j] = false;
                }
                else if (j == 0) {
                    dp[i][j] = true;
                }
                else if (nums[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][sum];
    }
}

3. Time & Space Complexity

时间复杂度O(n * sum), 空间复杂度O(n * sum)