一開始看到想到的解法是改編於 uva10364 的題目。
(1) 將所有的線段加總後的總長度做質因數分解，只保留因數的數值大於等於最大線段長
的數值 這些因數都可能是筷子的長度。
(2) 將輸入的線段由大到小排列，因數部分由小到大排列。 枚舉所有可能的因數直到成功
成功的定義為可以用所有的線段組出剛好邊長。
但是 d375-uva10364 的題目測資範圍只有20個片段組成，
這題最多會到達50個， 如果挑戰失敗意謂著會把所有可能嘗試過都無法組出來，
所以需要更好的剪枝來達成。
b597: Stickst(https://zerojudge.tw/ShowProblem?problemid=b597)
這是我寫的Code:https://www.codepile.net/pile/n1V8MnyY
不過會吃TLE，想問說還有哪部分可以剪枝但沒注意到。

1. 嘗試從最長開始排到最短的話呢，可以 greedy 如果有 [2, 3] 跟 [5] 的 sticks 可用，永遠先考慮拿 [5]2. 可以 DP 記住 [目前的根數] [iter 到哪一根] [目前這一根iter 多長]唔 我2. 好像有細節上的 bug 再想想2. 用 bitmask 雙向進行 BFS，狀態存 set，每次排出來看一下他的 complement是不是在另一頭BFS走過了BTW 檢定性質的 bi-BFS 有隨機性的算法，就是兩端隨便生m 條 k/2-path 然後meet-in-the-middle 比對

先排序然後從最小的因數開始測,去掉不可能的情形1. 除出來的組數超過陣列大小 2. 陣列最大值大於因數進行DFS時1.跳過重複的起點2.false的情形如果目前和為零表示不可能完成分組,直接early return3.每組的起點都由陣列中未使用的最大值開始

可以理解因數必須大於等於從片段中最長邊長但DFS的實作不是很清楚

比方說A = [1,1,1,1,2,3],最初的DFS從sum = 0, pos = 0跑這層的DFS會以for (int i = pos;)開始測A[i] + sum同一層DFS上一個拿來測的叫A[j]好了, 當A[i] == A[j]跳過意思是說同一個位置不需要測試相同長度的A[i]另外假設該層DFS sum = 0,但找不到解,就表示沒有任何組合可以滿足條件,就可以early return

感謝大大 雖然不吃TLE 不過還是WA 不知道哪邊掛掉第五組我會輸出83不過答案是1411，第七組是36答案是48附上code: https://www.codepile.net/pile/6KLP3mKo剛剛發現dfs寫錯，調整後還是tle QQ

質因數分解那一段不需要做, 直接從1開始測試use array不需要每次都memset,一開始做一次就好因為當A[i]不能拿來用,應該把use[i]還原DFS中的start應該由陣列尾端開始(Greedy)完成一個Group後,由陣列尾端往前找尚未使用的當下一層DFS的起點nowLen=0時,DFS又回傳false就要early return了不需要繼續iterate下去因為這表示該A[i]找不到任何解變數應該避免使用global variable, 容易錯

質因數分解的目的不是必須的嗎?這樣才能保證找到可以整除邊長的邊數和剪枝。for迴圈外面有個return false就是當現在不存一條邊滿足時就回傳false附上修改後的程式碼: https://www.codepile.net/pile/WKrglxeG

第 39 行 use[i] = 0; 下面增加一句if(nowLen == 0) break;

感謝 cutekid 和 CathyP 兩位大大耐心的指導和協助。感謝第一位回覆我的rareone大大，但我不太會雙向BFS和記憶化搜索方式，大概知道你說的方式附上實作：https://www.codepile.net/pile/ZOggAkOQ阿 2ms版本應該是測資較弱沒測出來，測資 : 15 34 3810 44 45 7 13 30 44 43 47 43 27 38 5答案是117

當你在測試 edgeLen 可不可行的時候可以用 DP 嗎？ 先找找有沒有一個 subset sum = edgeLen有的話 就拿掉那個 subset 然後 repeat 直到所有元素都用完為止， subset sum 用 DP 應該很容易作

應該無法，同樣是我舉例的測資，如果先移除(43,44,30)和(47,45,5,7,13)剩餘的片段無法構成兩個117

你的測資答案是161才對喔, 總和是483質因數分解不是必須 https://onlinegdb.com/S1e-oK7_V

第一個15是輸入15個數字的意思第40行程式碼是線性偵查目前的線段長度是不是總長度的因數，因為測資的總長度不超過2500所以無論是線性或是先做質因數分解找因數，時間差異不大。

那如果用 DP 先找出所有的 subset sum 然後再 DFS ？只是這樣做起來比較麻煩就是了從你原本的程式看起來 把 unused set 用 BST 存起來會不會比較方便找解答？

你的沒跑出117是出在line 39那邊沒檢查回傳值所以錯誤

感謝C大 那邊如果判斷失誤應該要還原use[i]的狀態根據FRAXIS大大的想應該是找出所有可以構成現在邊長用到的所有狀態集合，從這堆集合中找出一組存在每個片段只會用一次，這個問題等價於ZJ-a207需要用dancing link 解且存在狀態過多的風險。 我先理解一下a207的題目....