You are installing a billboard and want it to have the largest possible height. The billboard will have two steel supports, one on each side, and each support must have the exact same height.

You are given an integer array rods representing the lengths of rods that can be welded together. You can choose two disjoint subsets of rods to build the two supports such that both subsets have the same total sum. You do not need to use all available rods, and rods cannot be broken into smaller pieces.

Return the maximum possible height of the billboard. If it is not possible to construct two supports of equal height, return $0$.

Constraints:

• $1 \leq$ rods.length $\leq 20$

• $1 \leq$ rods[i] $\leq 1000$

• sum(rods[i]) $\leq 5000$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.