algorithm - 给定数字集合的所有可能的操作组合，总和为给定数字

Question

我发现很多帖子非常相似（指代币兑换问题），但只使用求和运算符。现在想象你可以加、减、乘和除，有没有办法让所有的计算组合得到一个给定的数字？理想情况下在 Java 中

示例：给定 1 5 2 4 9 尝试得到 16

解决方案：

• 9+1+4+2=16
• 2*9-(5-4+1)=16
• 5*(4+1)-9=16
• 依此类推（我找到了其中的 20 个）。

谢谢。

Answer 1

由于您只有二元操作，您可以将任何计算建模为二叉树，其中叶子是数字，所有其他节点都表示操作，例如对于您的前两个示例：

  +                  -
 / \                / \
9   +              *   +
   / \            /|  / \
  1   +          2 9 -   1
     / \            / \
    4   2          5   4

所以你的算法需要以下部分：

• 一个树生成器，用于所有可能的二叉树，直到某个节点数：从一个数字节点开始，递归地将每个数字节点（叶子）替换为一个运算符节点和两个子节点（数字节点），从而生成这样的树序列

.

N   O       O       O       ...
   / \     / \     / \
  N   N   O   N   N   O
         / \         / \
        N   N       N   N

• 为给定的二叉树（如上）生成所有可能的操作和数字插入的“树填充器”，例如：

.

  O    :    +     +    ...  -  ...
 / \       / \   / \       / \
N   N     1   5 1   2     1   5

• 计算结果的树评估器

快乐编程！:-)