Split Digits to Sum Closest To Target - Google Top Interview Questions

                        Solution in C++ :

int help(string& s, int target, int i, vector<vector<int>>& dp) {
    if (target < 0) {
        int ret = 0;
        for (int k = i; k < s.length(); k++) {
            ret += (s[k] - '0');
        }
        return ret - target;
    }
    if (i == s.length()) return target;
    if (dp[i][target] != -1) return dp[i][target];
    int ret = 1e6, curr = 0;
    for (int t = i; t < i + 4 and t < s.length(); t++) {
        curr = curr * 10 + s[t] - '0';
        ret = min(ret, help(s, target - curr, t + 1, dp));
    }
    return dp[i][target] = ret;
}
int solve(string s, int target) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(target + 1, -1));
    return help(s, target, 0, dp);
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(String s, int target) {
        Set<Integer>[] sets = new HashSet[s.length() + 1];
        for (int i = 0; i <= s.length(); i++) sets[i] = new HashSet<>();
        sets[0].add(0);
        for (int i = 0, i2 = 1; i != s.length(); i++, i2++) { // i2 is my index
            Set<Integer> seti = sets[i2];
            for (int j = 1; j <= 4; j++) {
                int start = i + 1 - j;
                if (start < 0)
                    break;
                final int val = Integer.parseInt(s.substring(start, i + 1));
                for (Integer prev : sets[start]) {
                    int nextval = prev + val;
                    if (nextval <= 2000)
                        seti.add(nextval);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int v : sets[s.length()]) res = Math.min(res, Math.abs(target - v));
        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, s, target):
        n = len(s)
        s = [int(c) for c in s]

        # For each index, precompute the index of the next nonzero digit.
        last = n
        next_nonzero = [0] * n
        for i in reversed(range(n)):
            if s[i] != 0:
                last = i
            next_nonzero[i] = last

        # Pick an arbitrary "bad" solution. We won't consider any solution worse than this one.
        baseline = abs(target - sum(s))

        @cache
        def dp(i, t):
            if i == n:
                # base case
                return abs(t)
            if s[i] == 0:
                # Skip leading zeroes, as they always contribute nothing.
                return dp(next_nonzero[i], t)

            ans = baseline
            cur = 0
            for j in range(i, n):
                cur = cur * 10 + s[j]
                if cur >= t + baseline:
                    break
                if j == n - 1 or cur != 0:
                    ans = min(ans, dp(j + 1, t - cur))
            return ans

        return dp(0, target)