Partition Equal Subset Sum

Medium

The problem

Return true if the numbers in nums can be split into two groups that have exactly the same sum. Every number must go into one of the two groups.

Example 1
Input: nums = [1, 5, 11, 5]
Output: true
[1, 5, 5] and [11] both add up to 11.
Example 2
Input: nums = [1, 2, 3, 5]
Output: false
The total is 11, which is odd, so it cannot be split evenly.

Limits

1 ≤ len(nums) ≤ 200
1 ≤ nums[i] ≤ 100

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

It is possible only if you can pick numbers that add up to exactly half of the total.

The idea

Subset-sum DP: reachable[0]=true; for each number update sums from the target down to the number (descending so each number is used once).

Target: O(n · sum/2) time

Go function shape

func canPartition(nums []int) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// CanPartition: split into two subsets with equal sums = can some numbers reach exactly half?
// reachable[s] means "some chosen numbers add up to s". Loop DOWNWARDS so each number is used once.
func CanPartition(nums []int) bool {
	total := 0
	for _, n := range nums {
		total += n
	}
	if total%2 != 0 {
		return false
	}
	half := total / 2
	reachable := make([]bool, half+1)
	reachable[0] = true
	for _, n := range nums {
		for s := half; s >= n; s-- {
			reachable[s] = reachable[s] || reachable[s-n]
		}
	}
	return reachable[half]
}

Read the lesson: Dynamic Programming