思路

枚举型dfs。暴力枚举搜索，通过枚举所有的可能数字组合形式来看是否符合要求。每次枚举当前数字和其符号，对于+或-直接在结果val上进行加减操作即可，但是对于就需要使用一个lastFactor变量存储上一个连乘的结果，当前value=value-lastFactor+curlastFactor(原理是首先将上一个+/-的数也就是连乘的数lastFactor还原回去，然后再将其与cur相乘加到value上)，并将其更新为lastFactor*cur。

需要注意： （1）对于第一个数字，只能默认为其符号为+，因此其递归参数path有所不同；对于其他位置开始的数字，分别枚举+/-/*的情况。 （2）需要去掉带有前导0的所有数字，也就是说0只能使用1次，一旦0与后面的任何一个数字结合为一个带有前导0的新字符串，就应该舍弃，因此在递归搜索之后（因为可以使用1次0，i每次递增1）加入对于cur的判断。 （3）由于中间结果可能溢出，所以cur和val都使用long类型。

代码

LintCode 653

public class Solution { /** * @param num: a string contains only digits 0-9 * @param target: An integer * @return: return all possibilities */ private void dfs(String num, int target, int start, String path, long val, long lastF, List<String> res) { if(start == num.length()) { if(val == target) { res.add(path); } return; } for(int i = start; i < num.length(); i++) { long cur = Long.parseLong(num.substring(start, i + 1)); if(start == 0) { dfs(num, target, i + 1, "" + cur, val + cur, cur, res); } else { dfs(num, target, i + 1, path + "*" + cur, val - lastF + lastF * cur, lastF * cur, res); dfs(num, target, i + 1, path + "+" + cur, val + cur, cur, res); dfs(num, target, i + 1, path + "-" + cur, val - cur, -cur, res); } // 对于任何带有前导0的数字组合即cur，都要被淘汰 // i.e.任何的0都能且仅能使用1次，一旦与后面的任何数字组合都要淘汰 if(cur == 0) { break; } } } public List<String> addOperators(String num, int target) { // write your code here List<String> res = new ArrayList<>(); if(num == null || num.length() == 0) { return res; } dfs(num, target, 0, "", 0, 0, res); return res; } }

复杂度

时间复杂度$O(n\ast 4^n)$: 见笔记或LC上的讲解 空间复杂度$O(n)$：不考虑res的大小，因为我们无法控制 We don’t consider the space occupied by the answers array since that is a part of the question’s requirement and we can’t reduce that in any way