How hard is LeetCode 282. Expression Add Operators?

LeetCode 282. Expression Add Operators is rated Hard on LeetCode.

What topics does LeetCode 282. Expression Add Operators cover?

LeetCode 282. Expression Add Operators is tagged Math, String and Backtracking on LeetCode.

Expression Add Operators — LeetCode 282 Python Solution

HardMathStringBacktracking

Problem: #282
Pattern: Backtracking
Reading time: 5 min
Source: leetcode.com

The problem

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value. Note that operands in the returned expressions should not contain leading zeros.

Example

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Python solution

Python

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        ans = []

        def dfs(u, prev, curr, path):
            if u == len(num):
                if curr == target:
                    ans.append(path)
                return
            for i in range(u, len(num)):
                if i != u and num[u] == '0':
                    break
                next = int(num[u : i + 1])
                if u == 0:
                    dfs(i + 1, next, next, path + str(next))
                else:
                    dfs(i + 1, next, curr + next, path + "+" + str(next))
                    dfs(i + 1, -next, curr - next, path + "-" + str(next))
                    dfs(
                        i + 1,
                        prev * next,
                        curr - prev + prev * next,
                        path + "*" + str(next),
                    )

        dfs(0, 0, 0, "")
        return ans

Complexity

Measure	Complexity
Time	Exponential (worst case)
Space	O(depth) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 282. Expression Add Operators is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 282. Expression Add Operators?: LeetCode 282. Expression Add Operators is rated Hard on LeetCode.
What topics does LeetCode 282. Expression Add Operators cover?: LeetCode 282. Expression Add Operators is tagged Math, String and Backtracking on LeetCode.