Question 1 (Minimum withdrawals - Solved, thanks to jan265):
There is a unique ATM in Wonderland. Imagine this ATM as an array of numbers. You can withdraw cash only from either ends of the array. Sarah wants to withdraw X amount of cash from the ATM. What are the minimum number of withdrawals Sarah would need to accumulate X amount of cash. If it is not possible for Sarah to withdraw X amount, return -1.
The first line contains an integer, N, denoting the number of elements in ATM.
Each line i of the N subsequent lines (where 0 <= i < N) contains an integer describing the cash in ATM.
The next line contains an integer, X, denoting the total amount to withdraw.
1 <= N <= 10^5
1 <= ATM[i] <= 10^5
1 <= X <= 10^5
Question 2 (Minimum pluses):
Given an equation “x=y”, for example, “111=12”, you need to add pluses inside x to make the equation correct. In our example “111=12”, we can add one plus “11+1=12” and the equation becomes correct. You need to find the minimum number of pluses to add to x to make the equation correct. If there is no answer print -1.
Note that the value of y won’t exceed 5000. The numbers in the corrected equation may contain arbitrary amounts of leading zeros.
The first line contains a string, A as described in the problem statement.
1 <= len(A) <= 10^3
I have tried to do these problems with backtracking, but the test cases are too large. I can only pass half the cases. How can I do this? Any hint will be appreciated.