# 17 lines solution, dfs (C++)

• ``````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, i-pos);
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, cv-now, now, '-');
dfs(res, num, target, cur+'*'+t, i, (op == '-') ? cv+pv - pv*now : ((op == '+') ? cv-pv + 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;
}
};``````

• Hi, cmyzx. Thanks for your sharing. Personally, this is the most clear solution I have found in the Discuss. The part handling `*` in the function `dfs` 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){
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);
}
}
``````

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

• Hi, cmyzx,

This solution cannot pass test case of sol.addOperators("2147483648", -2147483648);

• the size check probably is better I think. It avoids one more string equality call.

• Are you serious? Have you tested it on the OJ? The code just gets accepted... I guess you may have used `int` in the places where `long` should be used...

• 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 '-'.

• Well, the OJ has included this test case. In fact, you've misunderstood the problem, which says

add operators +, -, or * between the digits

So it makes no sense to just add a negative sign at the beginning.

• Can someone please help me understand why the past value during multiplication operation is not "now" instead its "pv*now" unlike other cases ? Thank you. - Reshmy

• Think about operator precedence. * has more precedence than +/-. If last one is +/- and current op is *, you have to do * first and then +/-.

• Can you explain me the multiplicative part of the solution. Thanks in advance.

• if (to_string(cur).size() != s.size()) continue; Could you explain this part? Thx

• 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:], current-now, tmpAns + '-' + num[:i], now, '-')

if pre_op == '+':
self.dfs(num[i:], current-pre_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)
``````

• If I replace op to '*' for multiplication instead of passing what was passed, I got wrong answer. Can anyone tell me why it is so?

• The value for multiplication of (pv*now) has already been calculated and you can regard this result as a new value that is associated with the previous operator ('+' or '-' or '#').

• 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, cv-n, -n, r+"-"+t, res);
dfs(s, target, pos+i, cv-pv+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?

• `if (to_string(cur).size() != s.size()) continue;`
`if (to_string(now).size() != t.size()) continue;`

No need to continue here, just break

• @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;
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.