The following DFS is similar to top solutions.

```
vector<string> addOperators(string num, int target) {
vector<string> exp;
string cur;
dfs(0,0,0,target,cur,num,exp);
return exp;
}
void dfs(int p, int prod, long res, int target, string& cur, string &num,vector<string>& exp) {
int n = num.size();
if(p==n && res==target) exp.push_back(cur);
long v = 0;
int sz = cur.size();
string s;
for(int i=p;i<n;i++) {
v=v*10+num[i]-'0';
s+=num[i];
if(cur.empty()) dfs(i+1,v,res+v,target,cur+=s,num,exp);
else {
dfs(i+1,v,res+v,target,cur+='+'+s,num,exp);
cur.resize(sz);
dfs(i+1,-v,res-v,target,cur+='-'+s,num,exp);
cur.resize(sz);
dfs(i+1,prod*v,res-prod+prod*v,target,cur+='*'+s,num,exp);
}
cur.resize(sz);
if(!v) return;
}
}
```

Time complexity O(4^n)

T(n) = 3 * T(n-1) + 3 * T(n-2) + 3 * T(n-3) + ... + 3 *T(1);

T(n-1) = 3 * T(n-2) + 3 * T(n-3) + ... 3 * T(1);

Thus T(n) = 4T(n-1);

Space complexity O(n)

Ignoring the large output, space complexity is depth of the recursion.

Most recursions can be speeded up by memorization. How about this one? No, because there is no duplicate states.

How about BFS? If a problem can be solved by one, we can solve it by the other. DFS has much lower memory requirements than BFS because it is not necessary to store all the children at each level. The search space is exponential so BFS space complexity is exponential which makes it not acceptable.