Minimum Subset Sum Difference

You are given an integer array nums. Partition every element into two groups so that the absolute difference between the sum of the first group and the sum of the second group is as small as possible.

Each element must go into exactly one of the two groups, and a group may be empty.

Return that minimum possible difference.

Examples

Example 1

Input: nums = [3,2,7,4,1]
Output: 1
Explanation: One group is {2, 3, 4} with sum 9 and the other is {1, 7} with sum 8.
The difference is |9 - 8| = 1, and no partition does better.

Example 2

Input: nums = [10]
Output: 10
Explanation: One group must hold the single element (sum 10) and the other is empty
(sum 0), so the difference is 10.

Example 3

Input: nums = [1,2,3,4]
Output: 0
Explanation: The groups {1, 4} and {2, 3} both sum to 5, so the difference is 0.