Problem description:

Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators '+', '-', or '*' between the digits of num so that the resultant expression evaluates to the target value.

Example 1:

1
2
Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]

Example 2:

1
2
Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]

Example 3:

1
2
Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

1
2
Input: num = "00", target = 0
Output: ["0*0","0+0","0-0"]

Example 5:

1
2
Input: num = "3456237490", target = 9191
Output: []

Constraints:

  • 1 <= num.length <= 10
  • num consists of only digits.
  • 231 <= target <= 231 - 1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        
        
        def backtracking(i: int = 0, prefix: str = '', value: int = 0, prev: int = 0):
            if i == len(num) and value == target:
                result.append(prefix)
                return None
            for j in range(i + 1, len(num) + 1):
                string = num[i:j]
                number = int(string)
                if string != '0' and num[i] == '0': # prevent "00*" as a number
                    print(string, num[i], i, j)
                    continue
                if not prefix:
                    backtracking(j, string, number, number)
                else:
                    backtracking(j, prefix + '+' + string, value + number, number)
                    backtracking(j, prefix + '-' + string, value - number, -number)
                    backtracking(j, prefix + '*' + string, value - prev + prev * number, prev * number)

        result = []
        backtracking()
        return result

time complexity: $O(3^n)$
space complexity: $O()$
reference:
related problem: