如何提出“子集运算”算法？

Question

我正在处理这个问题：

给定一个正数集(或多个集合)，找出集合中某些元素组合的所有数字。组合指和、减法或乘积。

例如，如果A= {3，4，7}，我们必须找出3，4，7，3+4，3*4，x-3-4，3+7，3*7，3*7倍，4+7，4*7，4*7，3+4+7，3+4*7，3+4-7倍，2，3+7-4倍.

幸运的是，我们的集合不大于10个数，但我无法找到一个算法来找到所有的解。你可以把这个问题看作是“子集和问题”(给定一个集合A和一个整数k，假设A包含一个元素和k的子集)，而不是和，它是一个算子的组合，我们希望找到所有可能的k-值。

我试过了，但是很多可能的解决方案都没有找到。这是不正确的，但我只想展示我的想法的实质：(C++代码)

vector<int> analyze (vector<int> v) {

    if (v.size()==1)    return v[0];
    vector<int> result;
    vector<int> u = analyze(v.delete(1));   //u = analyze(v[1], ..., v[n])
    for (int i = 0; i < u.size(); i++) {
        result.add(v[0] + u[i]);
        result.add(v[0] * u[i]);
        result.add(abs(v[0] - u[i]));
    }
    result.add(v[0]);
    return result + u;  //Union
}

如果A= {a，b，c，d}，此函数将不返回：

a*(c+b*d)

(a_b)+(c_d)

A-d+b

任何人都知道如何解决这个问题，或者任何有助于解决这个问题的参考书目？

Answer 1

我建议生成所有的解析树(没有必要显式地这样做)。

假设我们有一个初始集的子集。如果有一个号码，我们就把它还回去。否则，我们将遍历所有操作。对于固定操作，我们迭代所有方法将集合划分为两个子集。我们可以递归地计算子集的所有可能表达式，然后使用此操作组合它们。

考虑到不允许使用某些数字这一事实，我们可以对给定集合的所有子集运行此算法。