Solution
Approach 1: Dynamic Programming
Intuition
For each rod x
, we can write +x
, x
, or 0
. Our goal is to write 0
using the largest sum of positive terms. For writings that have a sum of 0
, let's call the sum of the positive terms written the score. For example, +1 +2 +3 6
has a score of 6
.
Since sum(rods)
is bounded, it suggests to us to use that fact it in some way. Indeed, if we already wrote some sum in the first few terms, it doesn't matter how we got it. For example, with rods = [1,2,2,3]
, we could arrive at a sum of 3
in 3 different ways, but the effective score is 3
. This upperbounds the number of states we have to consider to 10001
, as there are only this many possible sums in the interval [5000, 5000]
.
Algorithm
Let dp[i][s]
be the largest score we can get using rods[j]
(j >= i)
, after previously writing a sum of s
(that isn't included in the score). For example, with rods = [1,2,3,6]
, we might have dp[1][1] = 5
, as after writing 1
, we could write +2 +3 6
with the remaining rods[i:]
for a score of 5
.
In the base case, dp[rods.length][s]
is 0
when s == 0
, and infinity
everywhere else. The recursion is dp[i][s] = max(dp[i+1][s], dp[i+1][srods[i]], rods[i] + dp[i+1][s+rods[i]])
.
Complexity Analysis

Time Complexity: , where is the length of
rods
, and is the maximum of . 
Space Complexity: .
Approach 2: Meet in the Middle
Intuition
Typically, the complexity of brute force can be reduced with a "meet in the middle" technique. As applied to this problem, we have possible states, from writing either +x
, x
, or 0
for each rod x
, and we want to make this brute force faster.
What we can do is write the first and last states separately, and attempt to combine them. For example, if we have rods [1, 3, 5, 7]
, then the first two rods create up to nine states: [0+0, 0+3, 03, 1+0, 1+3, 13, 1+0, 1+3, 13]
, and the last two rods also create nine states.
We will store each state as the sum of positive terms, and the sum of absolute values of the negative terms. For example, +1 +2 3 4
becomes (3, 7)
. Let's also call the difference 3  7
to be the delta of this state, so this state has a delta of 4
.
Our high level goal is to combine states with deltas that sum to 0
. The score of a state will be the sum of the positive terms, and we want the highest score. Note that for each delta, we only care about the state that has the highest score.
Algorithm
Split the rods into two halves: left and right.
For each half, use brute force to compute the reachable states as defined above. Then, for each state, record the delta and the maximum score.
Now, we have a left and right halves with [(delta, score)]
information. We'll find the largest total score, with total delta 0
.
Complexity Analysis

Time Complexity: , where is the length of
rods
. 
Space Complexity: .