###### tags: `LeetCode` `DFS` `String` `Hard`
# LeetCode #282 [Expression Add Operators](https://leetcode.com/problems/expression-add-operators/)
### (Medium)

給定一個僅包含數字 0-9 的字符串 num 和一個目標值整數 target ，在 num 的數字之間添加 二元 運算符（不是一元）+、- 或 * ，返回所有能夠得到目標值的表達式。

---

在圖中可以看到, 使用curr儲存現有值, 並使用prev儲存上一個數字, 當接下來的運算符號為加減時, 可以很單純的更新現有值curr為curr+n, 並將prev更新為n。 但當運算符為乘號時, 由於乘號的運算優先度大於加減(並且連乘運算的值會合併, 所以上一個運算符只可能為加或減號), 此時需要先將curr減去(或加上)prev, 並將prev乘上n後再加回curr中。此外, 由於加減法分開寫有可能會出錯, 因此一律改用加法, 而減法部分則是將prev設為-n。

遞迴的中止條件為pos等於num的長度, 此時再額外檢查curr值是否等同於target, 若是則將tmp存入ans中, 之後不論額外檢查是否通過皆返回。

接下來對不同長度的數字皆進行運算遞迴呼叫, 提前跳過的條件有:(1)字串轉換成數字後大於整數上限, 此時跳出for迴圈(因為之後的值皆超過) (2)字串長度大於1, 但第一個字元為0(比如05, 012, 0234這種不符合數字格式的), 分割完後額外檢查, 若所引pos為0時, 代表是第一個數字, 不需要跟其他數字做額外運算, 因此需要特別的遞迴呼叫, 接下來分別呼叫"+", "-", "*", 規則照上面所述。

最後返回答案數組即可。

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> ans;
        dfs(num, target, 0, "", 0, 0, ans);
        return ans;
    }
    void dfs(const string& num, const int target, 
            int pos, const string& tmp, long prev, long curr,
            vector<string>& ans){
        if(pos==num.size()){
            if(curr==target)ans.push_back(tmp);
            return;
        }
        for(int l=1;l<=num.size()-pos;l++){
            string t =num.substr(pos, l);
            if(t[0]=='0'&&t.size()>1)break;
            long n = stol(t);
            if(n>INT_MAX)break;
            if(pos==0){
                dfs(num, target, l, t, n, n, ans);
                continue;
            }
            dfs(num, target, pos+l, tmp + '+' + t, n, curr + n, ans);
            dfs(num, target, pos+l, tmp + '-' + t, -n, curr - n,  ans);
            dfs(num, target, pos+l, tmp + '*' + t, prev*n, prev*n+curr-prev, ans);
        }
    }
};

---

(參考用)優化版, 使用同樣的參考exp來記錄字串, 並用len進行位置更新, 省去每次遞迴呼叫時的變數複製時間與空間。(沒完全搞懂為何修改exp[len++]=num[pos++]的位置調動會導致錯誤)

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> ans;
        string exp(num.size()*2, '\0');
        dfs(num, target, 0, exp, 0, 0, 0, ans);
        return ans;
    }
    void dfs(const string& num, const int target, 
            int pos, string& exp, int len, long prev, long curr,
            vector<string>& ans){
        if(pos==num.size()){
            if(curr==target)ans.push_back(exp.substr(0, len));
            return;
        }
        long n = 0;
        int s = pos;//startpoint
        int l = len;
        if(s!=0)++len;//l的位置放op, ++len放數字
        while(pos<num.size()){       
            n=n*10+(num[pos]-'0');
            if(num[s]=='0'&&pos-s>0)break;
            if(n>INT_MAX)break;
            exp[len++]=num[pos++];//使用num值更新exp <--
            if(s==0){
                dfs(num, target, pos, exp, len, n, n, ans);
                continue;
            }
            exp[l]='+'; dfs(num, target, pos, exp, len, n, curr + n, ans);
            exp[l]='-'; dfs(num, target, pos, exp, len, -n, curr - n,  ans);
            exp[l]='*'; dfs(num, target, pos, exp, len, prev*n, prev*n+curr-prev, ans);
        }
    }
};