algorithm - 回溯求和金字塔

Question

我正在尝试解决这个问题并且我是回溯算法的新手，问题是关于制作这样的金字塔，以便坐在两个数字上的数字是它们的总和。金字塔中的每个数字都必须不同且小于 100。像这样：

     88
   39  49
  15  24  25
 4  11  13  12
1  3   8   5   7 

关于如何使用回溯执行此操作的任何指示？

Answer 1

不一定是回溯，但您要求的属性与 Pascal Triangle 属性非常相似。

帕斯卡三角 (http://en.wikipedia.org/wiki/Pascal's_triangle) 用于高效计算二项式系数等，是一个金字塔，其中一个数字等于上述两个数字的总和它的顶部为 1。

如您所见，您正在询问相反的属性，其中数字是其下方数字的总和。

                1
              1   1
            1   2   1
          1   3   3   1
        1   4   6   4   1
      1   5  10  10   5   1
    1   6  15  20  15   6   1
  1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1

例如，在上面的帕斯卡三角形中，如果您希望金字塔的顶部为 56，那么您的金字塔将是从 56 开始的帕斯卡三角形底部向上的重建，这将给出如下内容：

                 56
              21    35
            6    15    20
         1     5    10    10

同样，这不是回溯解决方案，这可能无法为每个 N 提供足够好的解决方案，尽管我认为这是一个值得注意的有趣近似。