282. Expression Add Operators

exponential O(4ⁿ) time

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        n = size(num);
        string s(n << 1, 0); // 开一个buffer来拼结果
        dfs(0, 0, s, 0, num, 0, target);
        return res;
    }

private:
    void dfs(long sum, long last_num, string &s, int len, const string &num, int b, const int target) { // sum是当前计算结果，last_num是当前expr的最后一项，s是当前buffer状态，len是当前buffer中的expr的有效长度，b是当前剩余未扫描的num字符串的起始下标
        if (sum == target && b == n) {
            res.push_back(s.substr(0, len));
        }
        int l = len; // 因为要在当前expr基础上加optr，记录添加的位置
        if (b != 0) { // 因为第一个数字之前不能有optr，之后的才要给optr挪一个位置
            ++len;
        }
        long curr_num = 0;
        for (int i = b; i < n; ++i) {
            s[len++] = num[i]; // 往buffer里写入数字
            curr_num = curr_num * 10 + num[i] - '0';
            if (b == 0) { // 第一个数字前无optr，直接进入下一层递归
                dfs(curr_num, curr_num, s, len, num, i + 1, target);
            } else { // 添加optr然后进入下一层递归
                s[l] = '+'; dfs(sum + curr_num, curr_num, s, len, num, i + 1, target);
                s[l] = '-'; dfs(sum - curr_num, -curr_num, s, len, num, i + 1, target);
                s[l] = '*'; dfs(sum - last_num + last_num * curr_num, last_num * curr_num, s, len, num, i + 1, target);
            }
            if (num[b] == '0') break; // 数字不能以0开始
        }
    }

    int n;
    vector<string> res;
};

exponential O(n * 4ⁿ) time

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        dfs(0, 0, "", 0, num, target);
        return res;
    }

    void dfs(long sum, long last_num, const string &s, int b, const string &num, const int target) {
        if (sum == target && b == num.length()) {
            res.push_back(s);
        }
        string curr_s;
        long curr_num = 0; // 必须用long防止溢出
        for (int i = b; i < num.length(); ++i) {
            curr_s += num[i];
            curr_num = curr_num * 10 + num[i] - '0';
            if (b == 0) { // +3456-23-74+90是错的，第一个数字前不能有符号
                dfs(curr_num, curr_num, curr_s, i + 1, num, target);
            } else {
                dfs(sum + curr_num, curr_num, s + '+' + curr_s, i + 1, num, target);
                dfs(sum - curr_num, -curr_num, s + '-' + curr_s, i + 1, num, target);
                dfs(sum - last_num + last_num * curr_num, last_num * curr_num, s + '*' + curr_s, i + 1, num, target);
            }
            if (num[b] == '0') { // 数字不能以0开始，2534+034是错的
                break;
            }
        }
    }

    vector<string> res;
};