Description
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", "123"]
Example 2:
Input:
*num* ="232", target = 8
Output: ["23+2", "2+32"]
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
Backtracking, O(4 ^ n)
class Solution {
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
if (num == null || num.isEmpty()) {
return res;
}
helper(num, 0, target, 0l, 0l, "", res);
return res;
}
private void helper(String s, int start, int target, long eval, long multi, String path, List<String> res) {
if (start >= s.length()) {
if (eval == target) {
res.add(path);
}
return;
}
for (int i = start; i < s.length(); ++i) {
if (i > start && s.charAt(start) == '0') { // check if multiple digits started with zero
break;
}
long val = Long.parseLong(s.substring(start, i + 1)); // avoid overflow
// add operator before s.substring(start, i + 1)
if (start == 0) {
helper(s, i + 1, target, eval + val, val, String.valueOf(val), res);
} else {
helper(s, i + 1, target, eval + val, val, path + "+" + val, res);
helper(s, i + 1, target, eval - val, -val, path + "-" + val, res);
helper(s, i + 1, target, eval - multi + multi * val, multi * val, path + "*" + val, res);
}
}
}
}
