882. Twin Billboards
A billboard company wants to erect a banner held up by two steel supports of exactly the same height. It has a stock of poles with lengths rods. Each pole can be welded end to end onto one of the two supports or left unused; every pole is used at most once and cannot be cut.
Return the greatest possible common height of the two supports. If it is impossible to build two non-empty supports of equal height, return 0. The poles' total length is small, but there are too many ways to distribute them to try them all.
Example 1
- Input:
- rods = [3,5,8,2]
- Output:
- 8
- Explanation:
Weld 3 and 5 for one support (8) and use the single 8 for the other; the leftover 2 is not needed.
Example 2
- Input:
- rods = [6,9,4,7,12]
- Output:
- 19
- Explanation:
12 + 7 = 19 on one support and 6 + 9 + 4 = 19 on the other; no taller equal pair exists.
Example 3
- Input:
- rods = [4,10,25]
- Output:
- 0
- Explanation:
No subset sum of one group equals that of a disjoint non-empty second group (4, 10, 14, 25, ... are all distinct), so the answer is 0.
Constraints
- 1 ≤ rods.length ≤ 20
- 1 ≤ rods[i] ≤ 1000
- sum(rods) ≤ 5000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n * S)
- Space
- O(S)