0282. Expression Add Operators

https://leetcode.com/problems/expression-add-operators

Description

Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators '+', '-', or '*' between the digits of num so that the resultant expression evaluates 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:** []

Constraints:

• 1 <= num.length <= 10

• num consists of only digits.

• -231 <= target <= 231 - 1

ac1: brute force DFS

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        // edge cases
        if (num == null || num.length() == 0) return res;

        dfs(num, 0, 0, 0, true, target, "", res);

        return res;        
    }
    private void dfs(String num, int start, long val1, long val2, boolean plus, int target, String note, List<String> res) {
        long value = plus ? val1 + val2 : val1 - val2;
        // exit
        if (start >= num.length()) {
            if (value == target) res.add(note);
            return;
        }

        for (int i = start + 1; i <= num.length(); i++) {
            if (num.charAt(start) == '0' && i > start + 1) break; // "05" is not allowed, 0 is fine

            long curr = Long.parseLong(num.substring(start, i));

            if (start == 0) { // start point
                dfs(num, i, value, curr, true, target, "" + curr, res);
            } else {
                dfs(num, i, value, curr, true, target, note + "+" + curr, res);
                dfs(num, i, value, curr, false, target, note + "-" + curr, res);
                dfs(num, i, val1, val2 * curr, plus, target, note + "*" + curr, res);
            }
        }
    }
}

/*
backtracking find all result
*/