Code_Challenges/Day 11 at main · MrAtharvaB/Code_Challenges · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public ArrayList<String> findExpr(String num, int target) {
        ArrayList<String> res = new ArrayList<>();
        if (num == null || num.length() == 0) return res;
        dfs(res, "", num, target, 0, 0, 0);
        Collections.sort(res);
        return res;
    }

    private void dfs(ArrayList<String> res, String path, String num, int target, int pos, long eval, long prevNum) {
        if (pos == num.length()) {
            if (eval == target) {
                res.add(path);
            }
            return;
        }

        for (int i = pos; i < num.length(); i++) {
            if (i != pos && num.charAt(pos) == '0') break;
            String curStr = num.substring(pos, i + 1);
            long curNum = Long.parseLong(curStr);

            if (pos == 0) {
                dfs(res, curStr, num, target, i + 1, curNum, curNum);
            } else {
                dfs(res, path + "+" + curStr, num, target, i + 1, eval + curNum, curNum);
                dfs(res, path + "-" + curStr, num, target, i + 1, eval - curNum, -curNum);
                dfs(res, path + "*" + curStr, num, target, i + 1, eval - prevNum + prevNum * curNum, prevNum * curNum);
            }
        }
    }
}