雅虎搜狐創新工場微軟算法題(doc 8頁)

雅虎搜狐創新工場微軟算法題內容提要：
首先說一下這個題的解題思想。
1.選取某一個開始長度，開始組合小木棒，這個開始長度的限製條件為 不小於木棒最大長度，不大於所有木棒長度和，能被長度和整除
2.從可用的最長的那根小木棒開始組合木棒，找出所有的結果集，找到結果集後開始組合下一根木棒。
3.直到所有的小木棒都被組合完成，搜索結束。
思路：
1.len>=max{a[i]} && len|sum(a[i])
2.為了避免重複搜索，令每個大S的組成中，小S的長度依次遞減，這樣就需要在搜索之前對a[i]排序；全部的大S的第一段小S依次遞減
3.如果在某層搜索中，嚐試將a[j]加入到第i個大S的組成中，如果最終a[j]沒有被使用，且a[j+1]==a[j]，不需要繼續嚐試a[j+1]
4.如果此次是在嚐試第i個大S的第一段小S a[j]，a[j]為當前可以被使用的最長的小S，如果此次嚐試失敗，直接退出搜索，即退回到對第i-1個大S的搜索。試想：失敗說明現在使用a[j]是不可行的，那麼什麼時候使用a[j]呢？如果沒有退出搜索，肯定會在之後的搜索中使用a[j]，因為所有的小S必須都使用。之後的a[j]和最初嚐試的a[j]有什麼不同呢？沒有不同，它們等價，因此之後也不會成功，不需要繼續搜索。

..............................