#956
Tallest Billboard
candidate master · 1375 · lc hard +32 · verified · 51.8% accepted · 2,466 likes · top 41%
Description
A billboard needs two equal-height supports. From array rods, add each rod to either support or discard it. Find the greatest common height the two supports can reach, or return 0 if equal heights are impossible.
Example 1:
Input: rods = [1,2,3,6]
Output: 6
Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
Example 2:
Input: rods = [1,2,3,4,5,6]
Output: 10
Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
Example 3:
Input: rods = [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.
Code
1
2
3