LeetCode 282: Expression Add Operators

Explanation:

To solve this problem, we can use backtracking to explore all possible expressions by inserting the operators (+, -, *) between the digits of the given number. At each step, we can choose one of the operators and continue exploring the possibilities recursively. We also need to keep track of the current calculated value and the previous operand for multiplication.

Algorithm:

1. Start the backtracking process with initial parameters: current expression, current index in the input string, current calculated value, and previous operand for multiplication.
2. Iterate over the remaining digits from the current index onwards.
3. For each digit, consider all possible splits (no operator, +, -, *) and recursively explore the next digits.
4. Update the current expression, calculated value, and previous operand accordingly.
5. If the current index reaches the end of the input string and the calculated value matches the target, add the current expression to the result.
6. Continue exploring all possibilities until all digits are processed.

Time Complexity:

The time complexity of this approach is O(4^N) where N is the number of digits in the input string num. This is because for each digit, we have 4 choices (+, -, *, or no operator).

Space Complexity:

The space complexity is O(N) where N is the number of digits in the input string num for storing the intermediate results during backtracking.

:

import java.util.*;

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        backtrack(result, num, target, "", 0, 0, 0);
        return result;
    }

    private void backtrack(List<String> result, String num, int target, String expr, int index, long calculated, long prevOperand) {
        if (index == num.length()) {
            if (calculated == target) {
                result.add(expr);
            }
            return;
        }

        for (int i = index; i < num.length(); i++) {
            if (i != index && num.charAt(index) == '0') {
                break; // avoid leading zeros
            }
            long current = Long.parseLong(num.substring(index, i + 1));

            if (index == 0) {
                backtrack(result, num, target, expr + current, i + 1, current, current);
            } else {
                backtrack(result, num, target, expr + "+" + current, i + 1, calculated + current, current);
                backtrack(result, num, target, expr + "-" + current, i + 1, calculated - current, -current);
                backtrack(result, num, target, expr + "*" + current, i + 1, calculated - prevOperand + prevOperand * current, prevOperand * current);
            }
        }
    }
}