algorithm - 如何提出一个 "Subset operations"算法？

Question

我正在解决这个问题:

Given a set (or multiset) of positive numbers, find all the numbers which are combination of some elements from the set. Combination means sum, subtraction or product.

例如，如果 A = {3, 4, 7}，我们必须找到 3, 4, 7, 3+4, 3*4, |3-4|, 3+7, 3*7, | 3-7|, 4+7, 4*7, |4-7|, 3+4+7, 3+4*7, 3+|4-7|, |3+7-4|, |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)

(ab)+(cd)

|a-d|+b

任何人都知道如何解决这个问题，或者任何有帮助的引用书目？

Answer 1

我建议生成所有解析树(不需要明确地这样做)。

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

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