algo-aha

数字间加上加减乘，表达式结果等于某个数的所有可能

• https://leetcode.com/problems/expression-add-operators/

vector<string> addOperators(string num, int target) {
    vector<string> ans;
    search(num, target, 0, "", 0, 0, ans);
    return ans;
}

void search(string num, int target, int idx, string lastExprStr, 
            long lastExprVal, long lastNum, vector<string> &ans) {
    if (idx == num.size()) {
        if (lastExprVal == target) ans.push_back(lastExprStr);
        return;
    }

    // [idx..i]是currStr, [i+1..]进递归
    for (int i = idx; i < num.size(); i++) {
        if (i > idx && num[idx] == '0') continue; // 多位数不能以"0"开头
        auto currStr = num.substr(idx, i - idx + 1);
        long currNum = stol(currStr);
        if (idx == 0) {
            search(num, target, i + 1, currStr, currNum, currNum, ans);
        } else {
            search(num, target, i + 1, lastExprStr + "+" + currStr, 
                    lastExprVal + currNum, currNum, ans);
            search(num, target, i + 1, lastExprStr + "-" + currStr, 
                    lastExprVal - currNum, -currNum, ans);
            // 比如 lastExprVal=1+2+3，现在遇到*4，要lastExprVal-3+3*4
            // 若再遇到*5，要lastExprVal-(3*4)+(3*4)*5
            search(num, target, i + 1, lastExprStr + "*" + currStr, 
                    lastExprVal - lastNum + lastNum * currNum, lastNum * currNum, ans);
        }
    }
}

联系：表达式加括号的方式数只需要分治

24点游戏

• https://leetcode.com/problems/24-game/

穷举：从nums[]中任取两个数，遍历四种运算符，对每种运算符生成 arr[其余操作数, 此次运算结果]，在arr上递归。

bool judgePoint24(vector<int>& nums) {
    vector<double> v(nums.begin(), nums.end());
    return solve(v);
}

bool solve(vector<double>& nums) {
    const vector<char> ops = {'+', '-', '*', '/'};
    const int N = nums.size();
    const double EPSILON = 1e-6;
    if (N == 1) return abs(nums[0] - 24) < EPSILON;
    
    // 任取两个数
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;        
            // 先把剩下的数放入新数组
            vector<double> arr;
            for (int k = 0; k < N; k++) {
                if (k != i && k != j) {
                    arr.push_back(nums[k]);
                }
            }
            
            for (char op : ops) {
                if ((op == '+' || op == '*') && i > j) continue; // +*满足交换律，减少重复计算
                if (op == '/' && abs(nums[j]) < EPSILON) continue;
                
                double ans;
                if (op == '+') ans = nums[i] + nums[j];
                else if (op == '-') ans = nums[i] - nums[j];
                else if (op == '*') ans = nums[i] * nums[j];
                else if (op == '/') ans = nums[i] / nums[j];
                arr.push_back(ans);    
                if (solve(arr)) return true;
                arr.pop_back();
            }
        }
    }
    return false;
}