416. Partition Equal Subset Sum

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.

Solution:

The problem can be transformed to:

Can we find a subset that sum to sum / 2?

This is a classic dynamic programming problem.

The time complexity is O(n2) and the space complexity is O(n),



Code:

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