Standard Bar Dynamic Programming · DP on Subsequences O(n*S) · O(S)
A warehouse must load two trucks from one pallet queue, and the dispatch rule says the two loads should weigh as nearly the same as possible — perfect balance is rarely reachable. The scheduler therefore hunts for the split with the smallest gap between truck weights. Every pallet must go on one truck or the other.
Input: An integer n and an array arr of n non-negative integers.
Output: Return the minimum possible |sum(S1) - sum(S2)| over all partitions of arr into two sets.
1 <= n <= 1000 <= arr[i] <= 10^3the total sum stays within 10^4Input: {"n":4,"arr":[1,6,11,5]}
Output: 1
Sides {1, 5, 6} = 12 and {11} = 11 leave a gap of 1.
Input: {"n":3,"arr":[3,1,4]}
Output: 0
{3, 1} = 4 and {4} = 4 balance perfectly.