總和金字塔與回溯

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，但我認爲這是一個值得注意的有趣的近似值。