Two Equal Pillars

Hard

A sign needs two pillars of the same height, and the taller they are, the better. You have steel bars of lengths bars[i]. Bars can be welded end to end, so a pillar is as tall as the total length of the bars it is made of. Each bar can be used at most once: in one of the pillars, or not at all. Return the greatest height two equal pillars can have. If they cannot be built, return 0.

Example 1

bars=[2, 4, 5, 7] → 9

2 + 7 = 4 + 5 = 9: all four bars are used, and both pillars are 9 tall.

Example 2

bars=[3, 3, 10] → 3

Nothing can balance the 10, so it is left aside; the two 3s make pillars of height 3.

Example 3

bars=[4, 9] → 0

No two equal pillars can be built, so the answer is 0.

Constraints

1 ≤ len(bars) ≤ 20
1 ≤ bars[i] ≤ 1000
sum(bars) ≤ 5000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Water Between Walls Hard Biggest Solid Panel Block Hard Profit From Two Trades Hard Every Way to Space the Words Hard Crossing the Cave Hard

Input

bars=[2, 4, 5, 7]

Expected

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.