# Recursive Java solution using Map!

• ``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
if (input == null || input.length() < 1) {
return new ArrayList<Integer>();
}
Map<String, List<Integer>> map = new HashMap();
backtrack(input, 0, input.length() - 1, map);
return map.get(input);
}

private List<Integer> backtrack(String str, int start, int end, Map<String, List<Integer>> map) {
if (map.containsKey(str.substring(start, end + 1))) {
return map.get(str.substring(start, end + 1));
}
// check if string is integer
try {
int val = Integer.parseInt(str.substring(start, end + 1));
List<Integer> res = new ArrayList();
map.put(str.substring(start, end + 1), res);
return res;
} catch (Exception e) {
/* Ignore */
}
List<Integer> res = new ArrayList();
for (int i = start + 1; i < end; i++) { // 1 + 2 - 3
char ch = str.charAt(i);
if (ch == '-' || ch == '+' || ch == '*') {
List<Integer> left = backtrack(str, start, i - 1, map);
List<Integer> right = backtrack(str, i + 1, end, map);
for (int ll : left) {
for (int rr : right) {
int result = 0;
if (ch == '+') {
result = ll + rr;
} else if (ch == '-') {
result = ll - rr;
} else {
result = ll * rr;
}