Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

*Problem: *
https://www.geeksforgeeks.org/problems/expression-add-operators/1

Expression Add Operators

Difficulty: Hard Accuracy: 61.49%
Given a string s that contains only digits (0-9) and an integer target, return all possible strings by inserting the binary operator ‘ + ‘, ‘ – ‘, and/or ‘ * ‘ between the digits of s such that the resultant expression evaluates to the target value.
Note:

1. Operands in the returned expressions should not contain leading zeros. For example, 2 + 03 is not allowed whereas 20 + 3 is fine.
2. It is allowed to not insert any of the operators.
3. Driver code will print the final list of strings in lexicographically smallest order.
   Examples:
   Input: s = “124”, target = 9
   Output: [“1+2*4”]
   Explanation: The valid expression that evaluate to 9 is 1 + 2 * 4
   Input: s = “125”, target = 7
   Output: [“1*2+5”, “12-5”]
   Explanation: The two valid expressions that evaluate to 7 are 1 * 2 + 5 and 12 – 5.
   Input: s = “12”, target = 12
   Output: [“12”]
   Explanation: s itself matches the target. No other expressions are possible.
   Input: s = “987612”, target = 200
   Output: []
   Explanation: There are no expressions that can be created from “987612” to evaluate to 200.
   Constraints:
   1 ≤ s.size() ≤ 9
   s consists of only digits (0-9).
   -231 ≤ target ≤ 231-1

Solution:
class Solution:
def findExpr(self, s, target):
res = []
def backtrack(index, expr, value, last):
if index == len(s):
if value == target:
res.append(expr)
return
for i in range(index, len(s)):
if i != index and s[index] == ‘0’:
break
num = int(s[index:i+1])
if index == 0:
backtrack(i+1, str(num), num, num)
else:
backtrack(i+1, expr + ‘+’ + str(num), value + num, num)
backtrack(i+1, expr + ‘-‘ + str(num), value – num, -num)
backtrack(i+1, expr + ‘*’ + str(num), value – last + last * num, last * num)
backtrack(0, ”, 0, 0)
return sorted(res)