Expression Add Operators

LeetCode Q 282 - Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:
Input: num = "123", target = 6 ; Output: ["1+2+3", "1*2*3"]
Example 2:
Input: num = "232", target = 8 ; Output: ["2*3+2", "2+3*2"]
Example 3:
Input: num = "105", target = 5 ; Output: ["1*0+5","10-5"]
Example 4:
Input: num = "00", target = 0 ; Output: ["0+0", "0-0", "0*0"]
Example 5:
Input: num = "3456237490", target = 9191 ; Output: []

Solution : DFS

1. Corner Cases:

• if current position is 0, we can only use it as a single digit number, should be 0
• if it is not a single digit number with leading 0, it should be considered as an invalid number

2. How to do multiplication?
   we should subtract previous number, and then add current multiplication result to the subtraction result

Code:

List<String> res;

public List<String> addOperators(String num, int target) {
	res = new ArrayList<>();
	if (num == null || num.length() == 0)
	    return res;
	dfs(num, target, "", 0, 0, 0);
	return res;
}
    
private void dfs(String num, int target, String exp, int index, long prev, long calVal) {
	if (index == num.length() && calVal == target) {
		res.add(exp); return;
	} 
	
	for (int i = index + 1; i < num.length(); i++) {
		if (i != index && num.charAt(index) == '0') continue;
		long num = Long.parseLong(s.substring(index, i));
		if (i == 0) {
			dfs(num, target, exp + num, i, num, num);
		} else {
			dfs(num, target, exp + "+" + num, i, num, calVal + num);
			dfs(num, target, exp + "-" + num, i, -num, calVal - num);
			dfs(num, target, exp + "*" + num, i, prev * num, calVal - prev + prev * num);
		}
	}
}