15 Lines C++ DFS solution


  • 0
    B
    class Solution {
        void dfs(string &num, int start, int target, long sum, long prev, string inter, vector<string> &res) {
            if(start == num.length()) {
                if(sum == target) res.push_back(inter);
                return;
            }
            for(int end=start;end<num.length();end++) {
                if(num[start]=='0' && end != start) break;
                string s = num.substr(start, end-start+1);
                if(inter.empty()) dfs(num, end+1, target, stol(s), stol(s), s, res);
                else {
                    dfs(num, end+1, target, sum+stol(s), stol(s), inter+"+"+s, res);
                    dfs(num, end+1, target, sum-stol(s), -stol(s), inter+"-"+s, res);
                    dfs(num, end+1, target, sum-prev+prev*stol(s), prev*stol(s), inter+"*"+s, res);
                }
            }
        }
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> res;
            dfs(num, 0, target, 0, 0, "", res);
            return res;
        }
    };
    

Log in to reply
 

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