Expression Add Operators

Hard

0/120

0 upvote

Asked in company

Problem statement

You are given a string digits containing only the digits '0' through '9', and an integer target. Your task is to find all possible ways to insert the binary operators +, -, or * between the digits to form expressions that evaluate to the target value.

Rules for forming expressions:

1) Operators are placed between digits.
2) Operands (the numbers in the expression) can be formed by concatenating multiple digits. For example, in "123", you can form the operand 12.
3) Operands cannot have leading zeros, unless the number is 0 itself. For example, "105" can form 10, but "05" is invalid.

You need to return a list of all unique strings that represent these valid expressions.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains the string digits.

The second line contains the integer target.

Output Format:

Your function should return a list of strings, where each string is a valid expression. The runner code will handle printing each expression on a new line. If no solutions are found, nothing will be printed.

Note:

This problem requires a backtracking approach. A recursive helper function is needed to build the expression step-by-step.

Sample Input 1:

124
9

Sample Output 1:

1+2*4

Sample Input 2:

125
7

Sample Output 2:

1*2+5
12-5

Expected Time Complexity:

The expected time complexity is O(N * 4^N).

Constraints:

1 <= digits.length <= 10
-2^31 <= target <= 2^31 - 1

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Expression Add Operators

Console