Problem statement

https://binarysearch.com/problems/Split-Digits-to-Sum-Closest-To-Target/

Solution

Let dp[i] be all possible sums we can get if we use the first i elements from s. Notice that:

  1. If sum of all digits in s is more than target, than it is optimal to take this sum.
  2. If it is less than s, then it is never optimal to consider sums > 2*target - sm_min.
  3. From this it follows that when we split our string, length of split can not be more than log(target) + 1.

Complexity

Time is O(n * m * log m), where n = len(s) and m = target. Space is O(n * m).

Code

class Solution:
    def solve(self, s, target):
        sm_min = sum(int(i) for i in s)
        if sm_min >= target: return sm_min - target

        dp = defaultdict(set)
        dp[-1] = [0]
        n = len(s)
        for i in range(n):
            for x in range(min(4, i + 1)):
                for val in dp[i - x - 1]:
                    val2 = val + int(s[i-x:i+1])
                    if val2 <= 2*target - sm_min: dp[i].add(val2)

        return min(abs(target - x) for x in dp[n-1])