LeetCode Q282: Expression Add Operators (hard)

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.

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

Solution:
In my first try, I try to save all intermediate results of all possible cut, which equivalent to a BFS soluton. However, it result in a overflow of memory. Because BFS has to record all cases.

The problem can be solved using DFS, which is much more efficient in terms of memory usage. To deal with priority of operator "*", we need to keep track the operator used in last round. Also, we need to rule out the case where nums get multiple leading "0"s.