416. Partition Equal Subset Sum

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 416

Problem Statement

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100

Approach & Solution Steps

Brute force — 2^n subset sums.
Better — bitset / set of reachable sums — O(n * target) time.
Optimal — boolean 1D DP rolling over sums — O(n * target) time / O(target) space. <- pick this in interview.

Optimal JS Solution

function canPartitionFullTable(nums) {
	let total = 0;
	for (const value of nums) {
		total += value;
	}
	if (total % 2 === 1) return false;
	const target = total / 2;
	const length = nums.length;
	const table = Array.from({ length: length + 1 }, () =>
		new Array(target + 1).fill(false)
	);
	for (let index = 0; index <= length; index++) {
		table[index][0] = true;
	}
	for (let itemIndex = 1; itemIndex <= length; itemIndex++) {
		const value = nums[itemIndex - 1];
		for (let sum = 1; sum <= target; sum++) {
			if (sum < value) {
				table[itemIndex][sum] = table[itemIndex - 1][sum];
			} else {
				table[itemIndex][sum] =
					table[itemIndex - 1][sum] ||
					table[itemIndex - 1][sum - value];
			}
		}
	}
	return table[length][target];
}

function canPartition(nums) {
	let total = 0;
	for (const value of nums) {
		total += value;
	}
	if (total % 2 === 1) return false;
	const target = total / 2;
	const reachable = new Array(target + 1).fill(false);
	reachable[0] = true;
	for (const value of nums) {
		for (let sum = target; sum >= value; sum--) {
			if (reachable[sum - value]) {
				reachable[sum] = true;
			}
		}
	}
	return reachable[target];
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.