一开始看到想到的解法是改编于 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的题目....