以下是一道 Leetcode 题目：473.火柴到正方形（https://leetcode.com/problems/matchsticks-to-square/description/）
问题陈述
你有大小为n的数组matchsticks，每个数组包含不同的火柴长度。你想用所有火柴拼成一个正方形，但不能折断它们。如果可以，返回true。如果不能，返回false。
示例 1：
输入：火柴= [1,1,2,2,2]
输出：true
解释：你可以拼出一个长度为 2 的正方形，正方形的一边有两根长度为 1 的木棍。
示例 2：
输入：火柴= [3,3,3,3,4]
输出：false
解释：你无法找到用所有火柴组成一个正方形的方法。
限制：
1 <= n <= 15
1 <=火柴[i] <= 10^8
我见过这个问题的 O(4^n) 和 O(n*2^n) 解决方案。我通过一种在其他地方没有见过的解决方案以不同的方式解决了这个问题，我不确定它的时间复杂度是多少。我将使用matchsticks = [4, 4, 4, 3, 1] -> sideLength = 4的示例来解释解决方案。我用 C++ 解决了它。代码在最后：
我的解决方案：对于每一侧，遍历火柴棒数组，并针对每根火柴棒探索两个决策：将其添加到当前侧，不将其添加到当前侧。完成一侧后，转到下一侧，从头开始对火柴棒数组进行迭代（i=0）。由于每个元素有两个决策，我最初想说时间复杂度是 O(2^n)。整棵树的高度实际上不是n，但各个子树的高度最多是 n 。我在这里有点困惑。如何确定这种回溯解决方案的时间复杂度？
代码：
class Solution {
public:
bool makesquare(const std::vector<int>& matchsticks) {
int sum = 0;
for(int m : matchsticks)
sum += m;
if(sum % 4 != 0)
return false;
int sideLength = sum / 4;
std::vector<bool> available(matchsticks.size(), true);
return dfs(matchsticks, sideLength, 0, 0, available, 4);
}
bool dfs(const std::vector<int>& matchsticks, int sideLength, int currSideLength, int i, std::vector<bool>& available, int numRemainingSides) {
if(currSideLength == sideLength) {
currSideLength = 0;
numRemainingSides --;
i = 0; // restart choice of matches
if(numRemainingSides == 0)
return true;
}
if(i == matchsticks.size())
return false;
if(available[i]) {
// take current matchstick for the current side
available[i] = false;
if(dfs(matchsticks, sideLength, currSideLength + matchsticks[i], i+1, available, numRemainingSides))
return true;
// do not take the current matchstick for the current side
available[i] = true;
}
if(dfs(matchsticks, sideLength, currSideLength, i+1, available, numRemainingSides))
return true;
return false;
}
};
这是一个分析起来很复杂的算法，因为每次看到一个元素时，你都会做出二元选择。但这样你就最多可以看到 3 次相同的元素。这给出了一个微不足道的上限
O(8^n)。然而，如果你仔细想想，你会发现我们实际上把在 3 次传递中做出 4 个可能选择的问题分开了。如果我们不在第一遍或第二遍之后进行评估，而是只在第三遍结束时进行评估，我们最终会得到4^n组合，这需要付出O(4^n)努力。因此问题就成了，如果我们未能使第一或第二个优势发挥作用，那么停止继续前进会给我们带来多少好处？
我们可以从中心极限定理中获得一些直觉。假设它
n是 4 的倍数。有多少种方法可以将一组n东西分成两堆大小相等的东西？答案是O(2^n / sqrt(n))。那么有多少种方法可以将第一堆再次分成两堆大小相等的东西？答案是O(2^(n/2) / sqrt(n))。因此，如果我们按照边数而不是大小来计算，我们预计O(2^(3/2 n) / n)前两遍需要我们做O(2^(n/2))第三遍的工作。结果就是有O(4^n / n)工作。我相信，但无法证明这是最坏的情况。不过，我可以生成一系列对抗性输入，解决你的问题看起来与那个更简单的问题非常相似，并证明你无法做得比信封背面更好。
我的示例是以下对抗性输入系列：
一般来说，
kth 将包含3，然后4重复2k-2多次。然后16k-2, 16k-1, 16k+1, 16k+2。总和为
80k。您将尝试制作长度为 的边20k。这可以使用3、16k+1和 中k-1的任何元素来完成4。也可以使用5、16k-1和 中的任何k-1元素来完成4。这不能以任何其他方式完成，因为一旦您将16k-2或16k+2边相加，当您除以 4 时，您会得到余数为 2 的某个值。除了将另一个放入其中之外，没有其他方法可以消除该余数，但这样您就会得到长度为 的边32k，这太长了。n当然是4k+4。因为我们有4k-24， a3， a5，然后是 4 个大元素。当我们将这些对抗性输入放入你的算法中时会发生什么？
第一遍
O(2^n)按预期进行。（我会k在需要的地方和方便的时候使用。）除非我们决定包含最后 4 个元素中的两个，否则n我们真的不会成功。20k恰好
2 (4k-2 choose k-1)次，我们完美地完成了第一遍，然后尝试第二遍。每次我们这样做时，我们都有 3/4 的元素。这需要O(2^(3/4 n))。对于每一个，第二遍都成功了(3k-1 choose k-1)次。对于第一次和第二次成功传递的每一次，我们都会进行第三次传递。每次第三次传递都需要
O(2^(n/2))。最大的问题是
choose我们能得到多少个这样的 。因为这是一个很大的数字，所以我将改用对数。现在我们可以得出斯特林近似值。
所以
现在让我们让
O(1)错误过去。因此，m log(m + O(1))可以替换为m log(m)，(m + O(1))可以替换为m，并且1/2 log(O(1) m)可以替换为1/2 log(m)……现在收集同类项。有
k log(2)。8 - 2 = 6有k log(k)。4 - 2 - 2 = 0有log(k)。-2 + 2 - 1 = -1所以我们得到因此，第一遍和第二遍的组合数为（撤销对数），。
O(2^(6k) / k)记住，n = 4k + 4所以O(2^(6k) / k) = O(2^(3/2 n) / n)。然后，对于其中每一个，我们O(2^(n/2))在第三遍中再做一次工作，从而得到总共的O(2^(2n) / n) = O(4^n / n)工作。如果有人能将我的启发式方法修正为证明最坏情况不会比这更糟糕的证据，我将非常乐意给予他荣誉。