Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"] 

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

没想到的思路：

加个String path，当做参数之后 直接往结果里面加
long sum = sign? pre+current:pre-current; boolean类型的变量直接这么用
加个long pre,long current,boolean sign就行了。因为要处理不同符号的运算，这样更方便

 

这里先保存着pre,current*number，之后加减的时候再调用

一位接一位的时候需要。没有pos了这次，因为s = s.substring(i)不断缩短了

运算结果都是long类型

num.substring(0,i)和num.substring(i)是不一样的

退出的首要条件是s.length()==0，然后才是(int)sum == target,sum相等了就退出，不是cur相等了就退出

number * cur接着用之前的参数，cur，因为cur就是之前的number

class Solution {
    List<String> results = new ArrayList<String>();
    
    public List<String> addOperators(String s, int target) {
        //cc
        if (s == null || s == "")
            return results;
        
        //对于s的每一位进行for循环
        for (int i = 1; i <= s.length(); i++) {
            if (i >= 2 && s.charAt(0) == '0')
                continue;
            
        dfs(s.substring(i), s.substring(0, i), 0, Long.parseLong(s.substring(0, i)), target, true);
        }
        
        //返回结果
        return results;
    }
    
    public void dfs(String s, String path, 
                    long prev, long cur, int target, boolean operator) {
       
        //先定义好operator
        long sum = operator ? prev + cur : prev - cur;
        
        //exit
        if (s.length() == 0) {
            if (sum == (long) target) {
                results.add(path);
                return ;
            }
        }
        
        //对于s的每一位进行for循环
        for (int i = 1; i <= s.length(); i++) {
            if (i >= 2 && s.charAt(0) == '0')
                continue;
            
            long number = Long.parseLong(s.substring(0, i));
            
            dfs(s.substring(i), path + '+' + s.substring(0, i), sum, 
               number, target, true);
            dfs(s.substring(i), path + '-' + s.substring(0, i), sum, 
               number, target, false);
            dfs(s.substring(i), path + '*' + s.substring(0, i), prev, 
               number * cur, target, operator);
        }
    }
}

View Code