Shortest Java Backtrack solution without recursive For loop


  • 0
    O
    public List<String> addOperators(String num, int target) {
            List<String> res = new ArrayList<String>(); 
            if (num==null||num.length()==0) return res; 
            find(res, "", num, target, 0, 0, 0, 0); 
            return res; 
        }
        public void find(List<String> res, String path, String num, int target, int pos, long eval, long multed, long prev){
            if (pos==num.length()){
                if (target==eval) {
                    res.add(path);
                }
                return; 
            }
            int d = Character.getNumericValue(num.charAt(pos));
            if (pos==0||prev!=0){
                long cur = prev*10+d; long mult = (prev==0)?cur:multed/prev*cur;
                find(res, path+num.charAt(pos), num, target, pos+1, eval-multed+mult, mult, cur); 
            }
            if (pos>0){
                find(res, path+"+"+num.charAt(pos), num, target, pos+1, eval+d, d, d); 
                find(res, path+"-"+num.charAt(pos), num, target, pos+1, eval-d, -d, d); 
                find(res, path+"*"+num.charAt(pos), num, target, pos+1, eval-multed+multed*d, multed*d, d); 
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.