[数据结构与算法]LeetCode-每日一题 282. 给表达式添加运算符 [Java实现]

给定一个仅包含数字?0-9?的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、-?或?*?，返回所有能够得到目标值的表达式。

示例 1:

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]?

方法一：回溯

????????由题意，每一次对数的操作（截取1~n位）都存在 + - * 三种运算可能，对于 + - 两种操作，我们之间将 计算总值+/-当前截取数值 即可获取新的总值，而对于 * 这一运算，由于其具有的优先级，我们还需维护一个变量储存上一位截取值才能得出乘法下新的总值。

????????在示例代码中，我们维护一个 List 来便于对储存的字符串进行一系列的回溯操作（类似于一个栈，但比栈要更便捷

    private List<String> result;
    private char[] nums;
    private int target;

    public List<String> addOperators(String num, int target) {
        this.result = new ArrayList<>(1 << 3);
        this.nums = num.toCharArray();
        this.target = target;
        backtrace(0, 0, 0, new ArrayList<>(1 << 3));
        return result;
    }

    private void backtrace(int index, long preNumber, long correct, List<String> store) {
        if (index == nums.length) {
            if (correct == target) {
                StringBuilder builder = new StringBuilder();
                store.forEach(builder::append);
                result.add(builder.toString());
            }
            return;
        }
        for (int i = index; i < nums.length; ++ i) {
            if (i != index && nums[index] == '0') break;
            long number = Long.parseLong(new String(nums, index, i-index+1));
            if (index == 0) {
                store.add(String.valueOf(number));
                backtrace(i+1, number, number, store);
                store.remove(store.size()-1);
            } else {
                store.add("+" + number);
                backtrace(i+1, number, correct+number, store);
                store.remove(store.size()-1);

                store.add("-" + number);
                backtrace(i+1, -number, correct-number, store);
                store.remove(store.size()-1);

                store.add("*" + number);
                long multi = preNumber*number;
                backtrace(i+1, multi, correct-preNumber+multi, store);
                store.remove(store.size()-1);
            }
        }
    }