Partition Equal Subset Sum

LeetCode Q 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:

• Each of the array element will not exceed 100.
• 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 : DP

1. We calculate the sum of the array, if the sum cannot divided by two, then directly returning false.

2. boolean array dp[] is used to store the sum values of the array. If dp[sum / 2] can be achieved, then we can return true.

State Transfer Function
dp[i] = dp[i] || dp[i - nums[j]]; i: sum value;

Time Complexity: O(kn)
Time Complexity: O(kn)

Code:

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 == 1) return false;
	
	boolean[] dp = new int[sum / 2 + 1];
	dp[0] = true;

	for (int i = 1; i <= nums.length; i++) {
		for (int j = sum / 2; j >= nums[i - 1]; j--)
			dp[j] = dp[j] || dp[j - nums[i - 1]];
	}

	return dp[sum / 2];
}

Wrong Code:

for (int i = 1; i <= sum / 2; i++) { 
	for (int num: nums) {
		if (i >= num) dp[i] = dp[i] || dp[i - num];
	}
}

Since each num can only be used once, this code is wrong!!!