Partition Equal Subset Sum

Implement canPartition

Given an array of positive integers, determine whether it can be split into two subsets whose sums are equal. Every element must end up in exactly one of the two groups, and both groups together must use every element exactly once. An odd total can never be split evenly, so that case is ruled out immediately. Otherwise, finding an equal split is the same as finding any one subset that sums to exactly half the total — because whatever's left over automatically forms the other half, and since the two halves add up to the full total, matching one half automatically matches the other. That turns this into the familiar subset-sum search: try leaving each number out, try including it, and look for any combination that lands exactly on half the total.

Example 1:

Input: nums = [4,2,7,1,6]

Output: true

Example 2:

Input: nums = [9,4,6,3]

Output: false

Example 3:

Input: nums = [2,2,2]

Output: false

+ 7 hidden test cases run on Submit.

Constraints:

  • 1 ≤ nums.length ≤ 20
  • 1 ≤ nums[i] ≤ 100

nums =

[4, 2, 7, 1, 6]