# Simple DFS with mutually recursive methods (C++ 26 ms)

• This depth-first search implementation avoids some of the complexity of other DFS solutions by separating the search into 3 separate methods which call one another. Three variables are used to track state: currentInt which is the current integer being constructed, currentTerm which is the current multiplied product (negative if it's being subtracted, positive if it's being added), and currentOverall which is the sum of all terms before the current one.

``````class Solution {
// Handles digits that aren't the first digit in a number, and end of string
void dfsnum2(string& num, int i, int currentInt, int currentTerm, int currentOverall, int target, vector<string>& result) {
if (i == num.size()) {
if (currentOverall + currentTerm * currentInt == target) {
result.push_back(num);
}
return;
}

dfs(num, i, currentInt * currentTerm, currentOverall, target, result);

if (currentInt != 0) { // If it's zero, don't add more digits
int val = num[i] - '0';
if (currentInt <= (numeric_limits<int>::max() - val)/10) { // Check for overflow
dfsnum2(num, i + 1, currentInt * 10 + val, currentTerm, currentOverall, target, result);
}
}
}

// Handles digits that are the first digit in a number
void dfsnum(string& num, int i, int currentTerm, int currentOverall, int target, vector<string>& result) {
dfsnum2(num, i + 1, num[i] - '0', currentTerm, currentOverall, target, result);
}

// Handles operators
void dfs(string& num, int i, int currentTerm, int currentOverall, int target, vector<string>& result) {
num.insert(i, "+");
dfsnum(num, i+1, 1, currentOverall + currentTerm, target, result);
num.erase(i, 1);

num.insert(i, "-");
dfsnum(num, i+1, -1, currentOverall + currentTerm, target, result);
num.erase(i, 1);

num.insert(i, "*");
dfsnum(num, i+1, currentTerm, currentOverall, target, result);
num.erase(i, 1);
}

public:
vector<string> addOperators(string num, int target) {
vector<string> result;
if (num.length() == 0) {
if (target == 0) result.push_back("");
} else {
dfsnum(num, 0, 1, 0, target, result);
}
return result;
}
};
``````

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