hardDynamic Programming 1DPure DSA~45 min
Tallest Balanced Dual-Rail Support
You build two support rails from a set of rods, welding each rod onto either rail (or discarding it). The structure is valid only when both rails end at the same height. Maximize that common height.
Problem
Given an array rods of positive integers, partition a subset of them into two disjoint groups of equal sum and return that maximal equal sum (the height of one rail). If no non-empty balanced pair exists, return 0.
Input
An integer array rods.
Output
The maximum equal height of the two rails, or 0.
Constraints
- 1 ≤ n ≤ 20
- 1 ≤ rods[i] ≤ 1000
- sum(rods) ≤ 5000
Examples
Example 1
Input
[1,2,3,6]
Output
6
{1,2,3} and {6} both sum to 6.
Example 2
Input
[1,2]
Output
0
No way to make two equal non-empty rails.