Partition Set Into 2 Subsets with Min Absolute Sum Diff
Implement minSubsetSumDiff
Given an array of non-negative integers, split it into two groups — every element assigned to exactly one of the two — so that the absolute difference between the two groups' sums is as small as possible. Report that smallest possible difference.
Whatever one group sums to, the other group's sum is fixed: it's the total minus that amount. So the difference between the two groups is completely determined by just one group's sum, and minimizing that difference means finding whichever achievable sum for one group lands closest to exactly half the total. That reduces the problem to figuring out which sums are actually reachable by some subset of the array — the same reachability question as Subset Sum, just checked for every amount up to half the total instead of one specific target, then picking whichever reachable amount gets closest to that halfway point.
Example 1:
Input: nums = [4,9,6,2]
Output: 1
Example 2:
Input: nums = [10,20,15]
Output: 5
Example 3:
Input: nums = [5,5]
Output: 0
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 20 - ●
0 ≤ nums[i] ≤ 100
nums =
[4, 9, 6, 2]