总和金字塔与回溯

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 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，但我认为这是一个值得注意的有趣的近似值。