Minimum pluses required to make the equation (x = y) correct

The first thing that comes to mind is to have a table

int f[N+1][M+1];

where N = len(x) and M = y. Then f[i][j] would record the solution to the sub-problem substr(x,0,i)=j; i.e. how many pluses are needed to get the sum j from the first i digits of x. The table can be incrementally updated through the recurrence relation:

f[i][j] = minimum over 0 <= k < i of (f[k][j - atoi(substr(x,k,i))] + 1)

Configurations that aren't obtainable or out-of-bounds should be understood as having f[i][j] == +infinity rather than -1.

The size of the table will be O(N*M) and the running time is O(N² M).

I'll leave the implementation details and the starting condition for you to complete.

Backtracking along with DP (Memoization) helped me to pass all the cases here is my code. It passed all the cases in the given time limit

all_ans = {}
def min_pulses(A, target):
    
    if (A, target) in all_ans:
        return all_ans[(A, target)]
    
    if len(A) == 0:
        if target != 0:
            return -1
        else:
            return 0
        
    while len(A) > 0 and A[0] == '0':
        A = A[1:]
        
    if len(A) == 0 and target == 0:
        return 1
        
    if target < 0:
        return -1
    
    
    i = 1
    ans = float('inf')# initializing ans to infinite number so that min can be update
    
    while i <= 5 and i <=len(A):
        curr_num = A[:i]
        curr_ans = min_pulses(A[i:], target - int(curr_num))
        if curr_ans >= 0:
            ans = min(1 + curr_ans, ans)       
        
        i += 1
        
    if ans == float('inf'):
        ans = -1
        
        
    all_ans[(A,target)] = ans
    return ans

equation = input().split('=')
A = equation[0]
target = int(equation[1])

groups = min_pulses(A, target)

if groups < 0:
    print(-1)
    
else:
    print(groups - 1)

//import java.io.*;
import java.util.*;
//import java.lang.Math;

class NewClass15{
    
    public static int minimum_pluses(String S)
    {
        
        StringBuilder s = new StringBuilder();
        int target=0;
        for(int i=0;i<S.length();i++) //distinguishing left and right strings respectively
        {
            if(S.charAt(i)=='=')
            {
                target=Integer.parseInt(S.substring(i+1,S.length()));
                break;
            }
            s.append(S.charAt(i));
        }
        
        dp = new int[1000][5001][6];
        int temp = dfs(s.toString(),0,0,target);
        if(temp>=max)
            return -1;
        else
            return temp;
    }
    static int dp[][][];
    
    private static int dfs(String s,int len,int ind,int target)
    {
        if(target<0||len>5) return max;
        
        if(ind==s.length())
        {
            int x=0;
            if(len!=0)
                x=Integer.parseInt(s.substring(ind-len,ind));
            target-=x;
            
            if(target==0) return 0;
            
            return max;
              
        }
        
        if(dp[ind][target][len]!=0) 
        {
            System.out.println("1 dfs("+ind+","+target+","+len+")");
            return dp[ind][target][len]-1;
        }
        
        
        //add
        long ans=max;
        if(s.charAt(ind)=='0' && len==0)
        {
                        
            System.out.println("2 dfs("+0+","+(ind+1)+","+target+")");
            ans=Math.min(ans,dfs(s,0,ind+1,target));
            return (int)(ans);
        }
        
        System.out.println("3 dfs("+(len+1)+","+(ind+1)+","+target+")");
        ans=Math.min(ans,dfs(s,len+1,ind+1,target));
        
        //add +
        if(len!=0)
        {
            int x=Integer.parseInt(s.substring(ind-len,ind));
            int j=ind;
            while(j<s.length() && s.charAt(j)=='0') j++;
            
            if(j!=s.length()) j=j+1;
            
            System.out.println("4 dfs("+(1)+","+(j)+","+(target-x)+")");
            ans=Math.min(ans,1+dfs(s,1,j,target-x));
        }
        
        System.out.println("final dfs("+ind+","+target+","+len+")");
        dp[ind][target][len]=(int)(ans+1);
        return (int)(ans);
    }
    
    static int max=10000;

    public static void main(String[] args){
        
        Scanner scan = new Scanner(System.in);
        String A;
        A=scan.next();
        int result;
        result = minimum_pluses(A);
        System.out.print(result);
    }
}

This is the answer in java if it is of some help. I have not written the code though.

Can you provide me with some testcases for the given Minimum Pluses Question? Thank you.

"""2nd one Answer"""
def permute(s):
    result = [[s]]
    for i in range(1, len(s)):
        first = [s[:i]]
        rest = s[i:]
        for p in permute(rest):
            result.append(first + p)
    return [[int(j) for j in i] for i in result]
def problem(s):
    x,y=s.split("=")
    data=permute(x)
    newdata=[]
    for i in range(1,len(x)+1,1):
        for j in data:
            if i==len(j):
                newdata.append(j)
    for i in newdata:
        if sum(i)==int(y):
            print("str 1",i)
            return
    print("str -1")    
def check_constraint(s):
    if (not (1<=len(s)<=10^3)):
        print(-1)
    elif (s.split("=")[0]==s.split("=")[1]):
        print(1)
    elif (not (len(s.split("=")[0])>=len(s.split("=")[1]))):
        print(-1)
    else:
        problem(s)
A=input()
check_constraint(A)