public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList();
StringBuilder expression = new StringBuilder();
getExpressions(0, num, 0, 0, target, expression, res);
public void getExpressions(int startIndex, String num, long prevNum, long curRes, int target, StringBuilder expression, List<String> res) {
if (startIndex == num.length() && curRes == target) {
res.add(expression.toString());
int len = expression.length();
for (int i = startIndex; i < num.length(); i++) {
if (num.charAt(startIndex) == '0' && i != startIndex) break;
String curStr = num.substring(startIndex, i + 1);
Long curNum = Long.parseLong(curStr);
getExpressions(i + 1, num, prevNum * curNum, (curRes - prevNum) + (prevNum * curNum), target, expression.append("*").append(curNum), res);
expression.setLength(len);
getExpressions(i + 1, num, curNum, curRes + curNum, target, expression.append("+").append(curNum), res);
expression.setLength(len);
getExpressions(i + 1, num, -curNum, curRes - curNum, target, expression.append("-").append(curNum), res);
expression.setLength(len);
getExpressions(i + 1, num, curNum, curNum, target, expression.append(curStr), res);
expression.setLength(len);