1 public class Solution { 2     public List
     
       addOperators(String num, int target) { 3         List
      
        result = new ArrayList<>(); 4         if (num.length() < 2) { 5             return result; 6         } 7         getPath(result, "", num, target, 0, 0L, 0L); 8         return result; 9     }10     11     private void getPath(List
       
         result, String current, String num, int target, int pos, long value, long multi) {12         if (pos == num.length()) {13             if (target == value) {14                 result.add(current);15             }16             return;17         }18         19         for (int i = pos; i < num.length(); i++) {20             if (i != pos && num.charAt(pos) == '0') {21                 break;22             }23             long data = Long.parseLong(num.substring(pos, i + 1));24             if (pos == 0) {25                 getPath(result, current + data, num, target, i + 1, data, data);26             } else {27                 getPath(result, current + "+" + data, num, target, i + 1, value + data, data);28                 getPath(result, current + "-" + data, num, target, i + 1, value - data, -data);29                 getPath(result, current + "*" + data, num, target, i + 1, value - multi + multi * data, multi * data);30             }31         }32     }33 }
       
      
     

 

1. Deal with 0 situation : only 0 itself is allowed, it cannot be 04.

2. We have to record the previous value that can be used to extract from previous layer. For example 1234.

You calculate 1 + 2 + 3. Then you want add "*" between 3 and 4. You need to subtract 3 from the 1 + 2 + 3. And mutiple it with 4. So it would be (value - multi + multi * data)