操作从一组给定的数字，道达尔在给定数量的所有可能的组合 [英] All possible combinations of OPERATIONS from a given set of numbers that total to a given number

问题描述

我发现很多帖子非常相似（指硬币不断变化的问题​​），但仅使用的总和运营商。 现在想象一下，你可以加，减，乘，除，有没有办法让所有的计算组合到一个给定的数字？理想的情况是在Java中

I found a lot of post quite similar (referring to the Coin changing Problem) but only using the sum operator. Now imagine you can add, subtract, multiply and divide, is there a way to get all the calculation combinations to a given number? Ideally in Java

例： 鉴于1 5 2 4 9试图让16

Example: Given 1 5 2 4 9 try to get 16

解决方案：

• 9 + 1 + 4 + 2 = 16
• 2 * 9（5-4 + 1）= 16
• 5 *（4 + 1）-9 = 16
• 等等（我发现那些20）。

感谢。

推荐答案

既然你只有二进制运算，可以模拟任何计算作为一个二叉树，其中叶子是数字和所有其他节点重新presenting操作，如关于你的第两个例子：

Since you only have binary operations, you can model any of the calculations as a binary tree where the leaves are numbers and all other nodes are representing operations, e.g. for your first two examples:

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

所以，你的算法需要以下几部分组成：

So your algorithm would need the following parts:

• 一个树生成所有可能的二进制树达到一定节点计数：以数字开头的节点递归地与操作者节点和两个孩子（编号节点）替换每个编号节点（叶），由此产生的树的序像这样

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

• 在树填充物，它产生一个给定的二叉树（如上）的操作和数字的所有可能的插入，如：

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

• 在一棵树评估，计算结果

快乐编程！ ： - ）

Happy programming! :-)

这篇关于操作从一组给定的数字，道达尔在给定数量的所有可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！