Partition Equal Subset Sum

medium

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.

Test Cases

Copy an input into the main harness and Run to verify

Input

nums = [1,5,11,5]

Expected Output

true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Input

nums = [1,2,3,5]

Expected Output

false

Explanation: The array cannot be partitioned into equal sum subsets.

Constraints

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

Hints

Hint 1 — click to reveal

If the total is odd, no equal split can exist — return false immediately.

Hint 2 — click to reveal

Otherwise the question becomes: can any subset sum to total / 2? That is the 0/1 knapsack decision problem.

Java Compiler