C++实现算术凑目标数算法仅生成左联式无法找到解如何优化

你当前的算法采用的是单端增量拼接逻辑：每次仅将已生成的整体计算结果和单个未使用数字做运算，天然只能生成左侧持续嵌套的左联表达式，无法支持「多个独立子表达式分别计算后再合并」的结构（比如你举例的(2*5)*(44-3)就是两个子式先算完再相乘），因此会漏掉大量可行解。

改用子集合并递归法（也是类24点问题的标准解法），逻辑如下：

• 递归的输入不再是单个当前值和表达式，而是当前所有可用的「数值+对应表达式」列表
• 每次递归执行以下步骤：
  1. 如果当前列表仅剩1个元素，判断该元素的数值是否等于目标值，相等则找到解，记录表达式后终止所有递归
  2. 遍历列表中所有两两不同的元素对(a, b)
  3. 对每对元素尝试全部4种运算：
     • 加减乘三种运算可加溢出判断提前过滤无效计算
     • 除法需要额外判断除数不为0、且被除数可被除数整除
     • 减法、除法不满足交换律，需要同时尝试a op b和b op a两种情况
  4. 每次运算完成后，从列表中移除a、b两个元素，将运算得到的新数值和拼接好的表达式加入列表
  5. 传入新的列表执行下一层递归，递归返回后恢复原列表（回溯）

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Element {
    int val;
    string expr;
};

int Target = 302;
bool found = false;
string answer = "No Solution";
const char ops[4] = {'+', '-', '*', '/'};

int calc(int x, char op, int y, bool& valid) {
    valid = true;
    switch(op) {
        case '+': return x + y;
        case '-': return x - y;
        case '*': return x * y;
        case '/':
            if (y == 0 || x % y != 0) {
                valid = false;
                return 0;
            }
            return x / y;
        default: valid = false; return 0;
    }
}

void dfs(vector<Element> list) {
    if (found) return;
    int n = list.size();
    if (n == 1) {
        if (list[0].val == Target) {
            found = true;
            answer = list[0].expr;
        }
        return;
    }
    // 选两个不同的元素
    for (int i = 0; i < n && !found; i++) {
        for (int j = 0; j < n && !found; j++) {
            if (i == j) continue;
            // 尝试四种运算
            for (int op_idx = 0; op_idx < 4 && !found; op_idx++) {
                char op = ops[op_idx];
                // 交换律优化，加减乘只算一次i<j的情况避免重复计算
                if ((op == '+' || op == '*') && i > j) continue;
                bool valid;
                int res = calc(list[i].val, op, list[j].val, valid);
                if (!valid) continue;
                // 构建新列表
                vector<Element> new_list;
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) new_list.push_back(list[k]);
                }
                new_list.push_back({res, "(" + list[i].expr + op + list[j].expr + ")"});
                dfs(new_list);
            }
        }
    }
}

int main() {
    string input = "2 3 7 10 25 50";
    vector<Element> init_list;
    int num = 0;
    for (char c : input) {
        if (c == ' ') {
            init_list.push_back({num, to_string(num)});
            num = 0;
        } else {
            num = num * 10 + (c - '0');
        }
    }
    init_list.push_back({num, to_string(num)});
    dfs(init_list);
    cout << answer << endl;
    return 0;
}

上述代码可以覆盖所有合法的运算结构，只要存在解就一定能找到，同时做了交换律优化减少重复递归次数，找到解后会立刻终止所有递归避免无效计算。

内容的提问来源于stack exchange，提问作者caglarinhesap