Old Top Coder riddle: Making a number by inserting +

Question

I am thinking about this topcoder problem.

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual.

For example, consider "303" and a target sum of 6. The best strategy is "3+03".

I would solve it with brute force as follows:

for each i in 0 to 9 // i -- number of plus signs to insert
  for each combination c of i from 10
    for each pos in c // we can just split the string w/o inserting plus signs
      insert plus sign in position pos 
    evaluate the expression
    if the expression value == given sum
      return i

Does it make sense? Is it optimal from the performance point of view?

...

Well, now I see that a dynamic programming solution will be more efficient. However it is interesting if the presented solution makes sense anyway.

Answer 1

It's certainly not optimal. If, for example, you are given the string "1234567890" and the target is a three-digit number, you know that you have to split the string into at least four parts, so you need not check 0, 1, or 2 inserts. Also, the target limits the range of admissible insertion positions. Both points have small impact for short strings, but can make a huge difference for longer ones. However, I suspect there's a vastly better method, smells a bit of DP.