hardDynamic Programming 1DPure DSA~45 min
Tallest Equal-Height Dual Support Towers
You have steel rods of given lengths and want to build two support towers of EQUAL height using a subset of the rods (each rod assigned to at most one tower). Maximize that common height.
Problem
Given an array rods of rod lengths, you want to build two towers of equal height by welding rods together. Each rod can go to tower A, tower B, or be unused. Return the largest possible equal height of the two towers, or 0 if it is impossible to build any non-zero equal pair.
Input
An integer array rods of length [1, 20]; each length in [1, 1000]; sum of lengths <= 5000.
Output
An integer: the maximum equal tower height (0 if none).
Constraints
- 1 <= rods.length <= 20
- 1 <= rods[i] <= 1000
- sum(rods) <= 5000
Examples
Example 1
Input
rods = [1,2,3,6]
Output
6
{1,2,3} and {6} both reach height 6.
Example 2
Input
rods = [1,2]
Output
0
No equal-height split is possible.