1331. Partition Array into Two Subsets with Min Diff

Given an array of non-negative integers, split it into two subsets (either may be empty) so that the absolute difference of their sums is as small as possible, and return that minimum difference.

Input: A JSON object {"nums": [<non-negative integers>]}.

Output: Return the minimum possible absolute difference between the two subset sums.

Examples

Input: {"nums":[1,6,11,5]}
Output: 1
Explanation: Split {1,5,6} and {11} gives |12-11| = 1.

Input: {"nums":[1,2,3,9]}
Output: 3
Explanation: Best split {1,2,3} vs {9} gives 3.

Constraints

• 1 <= len(nums) <= 20
• 0 <= nums[i] <= 1000

Asked by