#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/lc-282-expression-add-operators-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/lc-282-expression-add-operators-implementation

Repovive

LeetCode 282 Expression Add Operators - Implementation - Coding Patterns II: Trees, Graphs & Advanced | Meta Interview Prep | Repovive

Repovive.

Meta Interview Prep6 sections · 147 units8h total

Open in Course

LeetCode 282 Expression Add Operators - Implementation

The code

Backtrack through all splits and operators. Track running value and last operand for multiplication.

Here's the solution:

function addOperators(num, target):
    results = []

    function backtrack(index, expr, val, prev):
        if index == len(num):
            if val == target:
                results.append(expr)
            return
        for i in range(index, len(num)):
            if i > index and num[index] == '0':
                break
            cur = int(num[index..i+1])
            if index == 0:
                backtrack(i+1, str(cur), cur, cur)
            else:
                backtrack(i+1, expr+"+"+str(cur), val+cur, cur)
                backtrack(i+1, expr+"-"+str(cur), val-cur, -cur)
                backtrack(i+1, expr+"*"+str(cur), val-prev+prev*cur, prev*cur)

    backtrack(0, "", 0, 0)
    return results

$O(4^n)$ time, $O(n)$ space for recursion where $n$ is the length of the string.