416. Partition Equal Subset Sum

Problem

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.

Problem Summary

Given a non-empty array containing only positive integers. Determine whether this array can be partitioned into two subsets such that the sum of the elements in both subsets is equal.

Note:

1. Each element in the array will not exceed 100
2. The size of the array will not exceed 200

Solution Approach

• Given a non-empty array in which all numbers are positive integers. Determine whether the elements of this array can be divided into two parts such that the sum of the numbers in each part is equal.
• This problem is a typical complete knapsack problem. Select certain items among n items to completely fill a knapsack of capacity sum/2.
• F(n,C) represents filling a knapsack of capacity C with n items, and the state transition equation is F(i,C) = F(i - 1,C) || F(i - 1, C - w[i]). If i - 1 items can already fill C, this case satisfies the requirement. At the same time, if i - 1 items cannot fill the knapsack, but after adding the i-th item it can exactly fill the knapsack, this also satisfies the requirement. The time complexity is O( n * sum/2 ) = O( n * sum).

Code

package leetcode

func canPartition(nums []int) bool {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum%2 != 0 {
		return false
	}
	// C = half sum
	n, C, dp := len(nums), sum/2, make([]bool, sum/2+1)
	for i := 0; i <= C; i++ {
		dp[i] = (nums[0] == i)
	}
	for i := 1; i < n; i++ {
		for j := C; j >= nums[i]; j-- {
			dp[j] = dp[j] || dp[j-nums[i]]
		}
	}
	return dp[C]
}