Leetcode 282

Coding question asked in Meta, Google, Amazon, and Microsoft interviews.

'''
Need to exhaust all the possibilities to find all the results.
In this case, we need to solve it with backtrack.

Need to define the recursive function:
scenario 1: extend current number by one digit without adding any operator
    - do not allow numbers start with 0, e.g. 05
scenario 2: add an operator +
scenario 3: add an operator -
    - must be added after one number
scenario 4: add an operator * 
    - must be added after one number

So we need the following parameters in the recursive function:
1. index - the current index of the num we are caculating on 
2. prevNum - the previous number, used for * operator
3. currentNum - the current number
4. currentSum - the current sum up to now
5. currentResult - the current result upto the current index
'''
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        res = []
        def recursive(index, prevNum, currentNum, currentSum, currentPath):
            if index == len(num):
                if currentSum == target and currentNum == 0:
                    res.append("".join(currentPath[1:]))
                return
            
            # extend the current number by one digit
            currentNum = currentNum * 10 + int(num[index])
            if currentNum > 0…