题解 | #给表达式添加运算符#

import java.util.*;


public class Solution {
    
    public class ComparaInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }

    HashSet<ArrayList<Integer>> hashSet = new HashSet<>();
    ArrayList<String> arrayList = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param num    string字符串
     * @param target int整型
     * @return string字符串一维数组
     */
    public String[] addOpt(String num, int target) {
        // write code here
        ArrayList<Integer> currentNumber = new ArrayList<>();
        splitString(currentNumber, num, 0);
        for (ArrayList<Integer> tmpArr : hashSet) {
            isEqualTarget(new StringBuffer(String.valueOf(tmpArr.get(0))), tmpArr, 1, target, tmpArr.get(0));
        }
        String[] ans = new String[arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++) {
            ans[i] = arrayList.get(i);
        }
        return ans;
    }

    public void splitString(ArrayList<Integer> currentNumber, String num, int index) {
        if (index >= num.length()) {
            ArrayList<Integer> copyArr = new ArrayList<>(currentNumber);
            copyArr.sort(new ComparaInteger());
            hashSet.add(copyArr);
            return;
        }
        if (num.charAt(index) == '0') {
            currentNumber.add(Integer.valueOf(0));
            splitString(currentNumber, num, index + 1);
            return;
        }
        for (int splitIndex = index + 1; splitIndex <= num.length(); splitIndex++) {
            currentNumber.add(Integer.valueOf(num.substring(index, splitIndex)));
            splitString(currentNumber, num, splitIndex);
            currentNumber.remove(currentNumber.size() - 1);
        }
    }

    public void isEqualTarget(StringBuffer currentString, ArrayList<Integer> currentNumber, int index, int target, int previousNum) {
        if (index >= currentNumber.size()) {
            if (previousNum == target) {
                arrayList.add(new String(currentString));
            }
            return;
        }
        StringBuffer copySB1 = new StringBuffer(new String(currentString));
        StringBuffer copySB2 = new StringBuffer(new String(currentString));
        // 加
        currentString.append("+" + currentNumber.get(index));
        isEqualTarget(currentString, currentNumber, index + 1, target, previousNum + currentNumber.get(index));
        // 减
        copySB1.append("-" + currentNumber.get(index));
        isEqualTarget(copySB1, currentNumber, index + 1, target, previousNum - currentNumber.get(index));
        // 乘
        copySB2.append("*" + currentNumber.get(index));
        isEqualTarget(copySB2, currentNumber, index + 1, target, previousNum * currentNumber.get(index));
    }
}