282.md

class Solution {

    public static void main(String[] args) {
        String num = "123456789";
        int target = 45;

        System.out.println(new Solution().addOperators(num, target));

    }

    private int target;
    private String num;

    public List<String> addOperators(String num, int target) {
        List<String> rst = new LinkedList<>();
        if (num == null || num.length() == 0) {
            return rst;
        }
        this.target = target;
        this.num = num;
        helper(rst, "", 0, 0, 0);
        return rst;
    }

    public void helper(List<String> rst, String path, int pos, long eval, long multed) {

        if (pos == num.length()) {
            if (target == eval) {
                rst.add(path);
            }
            return;
        }

        long value = 0;
        for (int i = pos; i < num.length(); i++) {
            if (i != pos && num.charAt(pos) == '0') {
                break;
            }
            value = value * 10 + num.charAt(i) - '0';
            if (pos == 0) {
                helper(rst, path + value, i + 1, value, value);
            } else {
                helper(rst, path + "+" + value, i + 1, eval + value, value);

                helper(rst, path + "-" + value, i + 1, eval - value, -value);

                helper(rst, path + "*" + value, i + 1, eval - multed + multed * value, multed * value);
            }
        }
    }
}

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().isAdditiveNumber("199100199"));
    }

    public boolean isAdditiveNumber(String num) {
        if (num.length() < 3) {
            return false;
        }

        return dfs(0, 0L, 0L, 0, num);
    }

    private boolean dfs(int index, long sum, long pre, int count, String nums) {
        if (index == nums.length()) {
            return count >= 3;
        }

        long value = 0L;
        for (int i = index; i < nums.length(); i++) {
            if (i > index && nums.charAt(index) == '0') {
                return false;
            }

            value = value * 10 + (nums.charAt(i) - '0');

            if (count >= 2) {
                if (value < sum) {
                    continue;
                } else if (value > sum) {
                    return false;
                }
            }

            boolean res = dfs(i + 1, pre + value, value, count + 1, nums);
            if (res) {
                return true;
            }
        }
        return false;
    }
}