AC Solution C++ short


  • 9
    Z
    class Solution {
    public:
        vector<string> addOperators(string num, int target) {
    		vector<string> ret;
    		if (num.length() == 0) return ret;
    		help(num, target, ret, num[0] - '0', num.substr(0, 1), 1, 1);
    		return ret;
    	}
    
    	void help(const string num, int target, vector<string> & v, long long last, string s, int idx, int left) {
    		if (target == last*left && idx == num.length())
    		{
    			v.push_back(s);
    			return;
    		}
    		else if (idx == num.length()) return;
    		else {
    			if(last!=0) help(num, target, v, last * 10 + num[idx] - '0', s + num.substr(idx, 1), idx + 1, left);
    			help(num, target, v, num[idx] - '0', s + '*' + num.substr(idx, 1), idx + 1, last*left);
    			help(num, target - left*last, v, num[idx] - '0', s + '+' + num.substr(idx, 1), idx + 1, 1);
    			help(num, target - left*last, v, num[idx] - '0', s + '-' + num.substr(idx, 1), idx + 1, -1);
    		}
    	}
    };

Log in to reply
 

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