1.可行性剪枝

枚舉的木棍長度要能整除木棒

2.優化搜索順序

木棍由大到小來排序,讓分支小的優先dfs

3.排除冗餘

3-1 已組合方式枚舉 避免排列

3-2 當前木棍假如無法拼湊,則之後木棍長度假如與當前長度相同,則必不可拼湊

3-3 假如當前是第i根木棒的第一個木棍,且此木棍導致無法拼湊,則就算跳過他,也必不可拼湊

3-4 假如當前是第i根木棒的最後一個木棍,且此木棍導致無法拼湊,則就算跳過他,也必不可拼湊

3-3 證明 

反證法

設當前木棒為i,當前這第一根木棍為j

假設跳過當前這根木棍j,使的拼湊成功,則i+1以後的木棒含有木棍j, 把i+1之後的木棍j移動到最前面在把整根木棒與第i根木棒調換

可得到j在木棒的隊頭時可拼湊成功,與原假設矛盾

3-4 證明

反證法

當前木棒為i,當前這最後一根木棍為j

假設跳過當前這根木棍j,使的拼湊成功,則當前第i根木棒有個若干個木棍加總=木棍j,所以可以與j調換,使的隊尾為j,與原假設矛盾