class Solution {
private:
// cur: {string} expression generated so far.
// pos: {int} current visiting position of num.
// cv: {long} cumulative value so far.
// pv: {long} previous operand value.
// op: {char} previous operator used.
void dfs(std::vector<string>& res, const string& num, const int target, string cur, int pos, const long cv, const long pv, const char op) {
if (pos == num.size() && cv == target) {
res.push_back(cur);
} else {
for (int i=pos+1; i<=num.size(); i++) {
string t = num.substr(pos, ipos);
long now = stol(t);
if (to_string(now).size() != t.size()) continue;
dfs(res, num, target, cur+'+'+t, i, cv+now, now, '+');
dfs(res, num, target, cur+''+t, i, cvnow, now, '');
dfs(res, num, target, cur+'*'+t, i, (op == '') ? cv+pv  pv*now : ((op == '+') ? cvpv + pv*now : pv*now), pv*now, op);
}
}
}
public:
vector<string> addOperators(string num, int target) {
vector<string> res;
if (num.empty()) return res;
for (int i=1; i<=num.size(); i++) {
string s = num.substr(0, i);
long cur = stol(s);
if (to_string(cur).size() != s.size()) continue;
dfs(res, num, target, s, i, cur, cur, '#'); // no operator defined.
}
return res;
}
};
17 lines solution, dfs (C++)


Hi, cmyzx. Thanks for your sharing. Personally, this is the most clear solution I have found in the Discuss. The part handling
*
in the functiondfs
is really fascinating :)BTW, this line
if (to_string(now).size() != t.size()) continue;
can just be shortened a little bit to:
if (to_string(now) != t) continue;

public List<String> addOperators(String num, int target) { List<String> result = new ArrayList<String>(); //search each possible left start number for(int i = 1; i <= num.length(); i++){ String left = num.substring(0, i); long left_long = Long.valueOf(left); if(!(left_long + "").equals(left)) break;//if it starts with multiyple 0s, skip them all DFS(num, i, target, left, left_long, left_long, '#', result); } return result; } public void DFS(String num, int index, int target, String leftExpr, long leftValue, long prevValue, char sign, List<String> result){ //if we reach end of string and left value equals target if(index == num.length() && target == leftValue){ result.add(leftExpr); return; } //start from index + 1, end at num.length, the input index is already the first index after left for(int i = index+1; i <= num.length(); i++){ String right = num.substring(index, i); long right_long = Long.valueOf(right); if(!(right_long + "").equals(right)) return;//if it starts with multiple 0s, skip them all //operator between left and right is "+" DFS(num, i, target, leftExpr + "+" + right, leftValue + right_long, right_long, '+', result); //operator between left and right is "" DFS(num, i, target, leftExpr + "" + right, leftValue  right_long, right_long, '', result); //operator between left and right is "*", then we merge this * with right to left long newLeft = 0; if(sign == '+'){ //remove last number, add last number * current right newLeft = leftValue  prevValue + prevValue * right_long; }else if (sign == ''){ newLeft = leftValue + prevValue  prevValue * right_long; }else{//inital case, first left, where we don't have +/ before it newLeft = prevValue * right_long; } //since we merge a * b to a new a, we will keep the sign before a DFS(num, i, target, leftExpr + "*" + right, newLeft, prevValue*right_long, sign, result); } }
Cool Solution! I write your solution in Java and add comments.
Basically, you recursively expand left operand and keep last number added into the left. So if the next
operator is "*", you can update the last number in left accordingly

It looks like that leetcode doesn't check this test case. Even though the above code pass OJ, I run the codes on my machine, the return result is empty which is wrong. In the first iteration, it always push the number into string directly, there's no way to generate string starting with ''.

Great answer! here's python version
def addOperators(self, num, target): self.ans = [] self.target = target for i in xrange(1, len(num)+1): if i > 1 and num[0] == '0': continue self.dfs(num[i:], int(num[:i]), num[:i], int(num[:i]), '#') return self.ans def dfs(self, num, current, tmpAns, pre_val, pre_op): if not num: if self.target == current: self.ans.append(tmpAns) return for i in xrange(1, len(num)+1): if i > 1 and num[0] == '0': continue now = int(num[:i]) self.dfs(num[i:], current+now, tmpAns + '+' + num[:i], now, '+') self.dfs(num[i:], currentnow, tmpAns + '' + num[:i], now, '') if pre_op == '+': self.dfs(num[i:], currentpre_val + pre_val*now, tmpAns + '*' + num[:i], pre_val*now, pre_op) elif pre_op == '': self.dfs(num[i:], current+pre_val  pre_val*now, tmpAns + '*' + num[:i], pre_val*now, pre_op) else: self.dfs(num[i:], current * now, tmpAns + '*' + num[:i], pre_val*now, pre_op)

Nice solution! I rewrite in C++ with less code.
class Solution { public: vector<string> addOperators(string num, int target) { vector<string> res; dfs(num, target, 0, 0, 0, "", res); return res; } void dfs(string& s, int target, int pos, long cv, long pv, string r, vector<string>& res) { if (pos == s.size() && cv == target) { res.push_back(r); return; } for (int i = 1; i <= s.size()  pos; i++) { string t = s.substr(pos, i); if (i > 1 && t[0] == '0') continue; // preceding long n = stol(t); if (pos == 0) { dfs(s, target, i, n, n, t, res); continue; } dfs(s, target, pos+i, cv+n, n, r+"+"+t, res); dfs(s, target, pos+i, cvn, n, r+""+t, res); dfs(s, target, pos+i, cvpv+pv*n, pv*n, r+"*"+t, res); } } };

Nice solution, can you please share the thought process of deriving how to handle substrings? When I first look at the problem, the first thing came to my mind is to get all combinations of digits first, then for each combination do the DFS.
How did you manage to make sure you cover all substrings and dfs in the same logic?

@huanyan_hny Exactly, I am thinking the same way. In that case, it can save some iterations. My code accepted with the following conditions:
if (to_string(nowVal).length() != t.size()) break;