How to calculate two equal sums from an array of random natural numbers?

Question

JavaScript

Hello, I came across such an interesting problem:

You are going to install a billboard and you want it to have the highest height. The billboard rests on two steel supports, one on each side. The supports must be the same height.

You have a collection of rods that can be welded together. For example, if you have rods of length 1, 2 and 3, you can weld them together to make a support of length 6.

Return the billboard to the maximum possible height. If you can't place the billboard, return 0.

In: rods - an array with the lengths of the available rods

. Out: the maximum height of the billboard, or 0 if it's impossible to get the same height of supports.

Example:
1.

const rods = [1,2,3,6]
getHeight( rods ) // 6

from this set of rods we can get two supports of 6: by welding the rods with a length of 1,2,3 and using the existing rod with a length of 6

2.

const rods = [1,2]
getHeight( rods ) // 0

from this set of rods it is impossible to get two supports of the same length

Answer 1

This task is a variant of Subset sum problem .
It is NP-complete - there are no quick and easy solutions. In the general case, only an exhaustive search for N * 3 ^ N is possible. Something like what Alexandroppolus suggested , except that the case where the current number is simply skipped is not considered at all. You can also do the same without recursion based on bit masks. If there are some additional conditions (for example, all numbers are very small), then a dynamic programming solution, as in the knapsack problem
, may be faster .