class Solution { List<String> res = new ArrayList<>(); public List<String> addOperators(String num, int target) { dfs(num,0,"",target,0,0); return res; } public void dfs(String num, int index, String s, int target, long sum, long pre) { if(index == num.length()) { if(target == sum) { res.add(s); } return; } // 枚举当前数可能的所有取值 for(int i = index; i < num.length(); i++) { // 当前数位大于1且以0开头直接返回 if(num.charAt(index) == '0' && i > index) return; long cur = Long.parseLong(num.substring(index,i+1)); if(index == 0) { // index==0说明是第一个数,特殊处理 dfs(num,i+1,s+cur,target,sum+cur,cur); } else { // 三种情况回溯 dfs(num,i+1,s+'+'+cur,target,sum+cur,cur); dfs(num,i+1,s+'-'+cur,target,sum-cur,-cur); dfs(num,i+1,s+'*'+cur,target,sum-pre+pre*cur,pre*cur); } } } }