以下是Leetcode問題：473。火柴棒到廣場(https://leetcode.com/problems/matchsticks-to-square/description/)
Problem Statement
你有一個(gè)數(shù)組，火柴棒，大小為n，長度不同。你想用所有的火柴棒創(chuàng)建一個(gè)正方形，而不打破它們。如果可以，返回true。如果不能，返回false。
Example 1:
- 輸入：火柴棒=[1,1,2,2,2]
Output: true
- 說明：你可以形成一個(gè)長度為2的正方形，正方形的一邊有兩根長度為1的棍子。
Example 2:
- 輸入：火柴棒=[3,3,3,4]
Output: false
- 說明：你找不到用所有火柴棍組成正方形的方法。
Constraints:
- 1<=n<=15
- 1<=火柴棒[i]<=10^8
我已經(jīng)看到了這個(gè)問題的O（4^n）和O（n*2^n）解。我通過一個(gè)在其他任何地方都沒有看到的解決方案以不同的方式解決了這個(gè)問題，我不確定它的時(shí)間復(fù)雜度是多少。我將用火柴棒=[4,4,4,4,3,1]->sideLength=4來解釋這個(gè)解決方案。我用C++解決了這個(gè)問題。代碼位于末尾：
我的解決方案：對于每一方，迭代火柴棒數(shù)組，并對每一根火柴棒探索兩個(gè)決定：將其添加到當(dāng)前側(cè)，而不是將其添加至當(dāng)前側(cè)。完成一個(gè)邊后，繼續(xù)下一個(gè)邊，從開始（i=0）開始對火柴棒數(shù)組進(jìn)行迭代。由于每個(gè)元素有兩個(gè)決策，我最初想說時(shí)間復(fù)雜度為O（2^n）。整棵樹的高度不是n，但單個(gè)子樹的高度最多是n。我在這里有點(diǎn)困惑。如何確定這種回溯解決方案的時(shí)間復(fù)雜度？
Code:
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;
}
};
這是一個(gè)復(fù)雜的算法，因?yàn)槊看文憧吹揭粋€(gè)元素，你都會做出二元選擇。但隨后，您可能會看到同一元素多達(dá)3次。這給出了一個(gè)微不足道的上限
O(8^n)。然而，如果你仔細(xì)想想，你會發(fā)現(xiàn)我們真的把在3次傳球中做出4個(gè)可能選擇的問題分開了。如果我們在第一次或第二次傳球后不進(jìn)行評估，而只在第三次傳球結(jié)束時(shí)進(jìn)行評估，我們最終會得到4^n個(gè)組合，這需要O(4^n)個(gè)工作。因此，問題就變成了，如果我們不能發(fā)揮出我們的第一或第二優(yōu)勢，我們不繼續(xù)下去能獲得多少收益？
我們可以從中心極限定理中得到一些直覺。假設(shè)
n是4的倍數(shù)。有多少種方法可以將一組n的東西分成兩堆大小相等的東西？答案是O(2^n / sqrt(n))。那么，有多少種方法可以將第一堆再次分成兩堆大小相等的樁呢？答案是O(2^(n/2) / sqrt(n))。因此，如果我們按邊的數(shù)量而不是大小來計(jì)算，我們預(yù)計(jì)前兩遍需要O(2^(3/2 n) / n)個(gè)邊，而第三遍需要O(2^(n/2))個(gè)邊。這導(dǎo)致了O(4^n / n)個(gè)邊的工作量。我相信，但不能證明這是最壞的情況。然而，我可以產(chǎn)生一系列對抗性的輸入，解決你的問題看起來很簡單，并證明你不能做得比信封后面更好。
我的例子是以下一系列對抗性輸入：
一般來說
kth將包含3，然后4重復(fù)2k-2次。然后16k-2, 16k-1, 16k+1, 16k+2。這等于
80k。您將嘗試制作長度為20k的邊。這可以用3、16k+1和4元素中的任何k-1來完成。它也可以用5、16k-1和4元素中的任何k-1來完成。它不能以任何其他方式完成，因?yàn)橐坏┠慵由?code>16k-2或16k+2邊，當(dāng)你除以4時(shí)，你就會得到余數(shù)為2的結(jié)果。除了把另一條邊放進(jìn)去，沒有辦法去掉剩下的部分，但你會得到一條長度為32k的邊，這太長了。n當(dāng)然是4k+4。因?yàn)槲覀冇?code>4k-24個(gè)元素，3個(gè)，5個(gè)，然后是4個(gè)大元素。當(dāng)我們將這些對抗性輸入放入你的算法中時(shí)會發(fā)生什么？
第一次傳球按預(yù)期進(jìn)行了
O(2^n)。（我會在必須的地方使用k，在convenient.的時(shí)候使用n）除非我們決定包含最后4個(gè)元素中的兩個(gè)，否則我們真的不會達(dá)到20k。整整
2 (4k-2 choose k-1)次，我們完美地完成了第一遍，并嘗試了第二遍。每次我們這樣做，我們都有3/4的元素。這需要O(2^(3/4 n))。對于每一個(gè)，第二次傳遞都會成功(3k-1 choose k-1)次。對于每一次成功的第一次和第二次傳球，我們都會進(jìn)行第三次傳球。然后，每三次傳球都需要
O(2^(n/2))。最大的問題是，我們能得到多少這樣的人。因?yàn)檫@是一個(gè)很大的數(shù)字，我將切換到對數(shù)。
現(xiàn)在我們可以得出斯特林近似。
And so
現(xiàn)在讓我們傳遞
O(1)個(gè)錯(cuò)誤。因此，m log(m + O(1))可以替換為m log(m)，(m + O(1))可以替換成m，而1/2 log(O(1) m)可以替換成為1/2 log(m)。。。現(xiàn)在收集類似的術(shù)語。
k log(2)有8 - 2 = 6。k log(k)有4 - 2 - 2 = 0。而log(k)有-2 + 2 - 1 = -1。所以我們得到因此，第一和第二遍的組合數(shù)量為（撤消日志）
O(2^(6k) / k)。記住n = 4k + 4和O(2^(6k) / k) = O(2^(3/2 n) / n)。然后，對于每一個(gè)，我們在第三遍做另一個(gè)O(2^(n/2))項(xiàng)工作，總共完成O(2^(2n) / n) = O(4^n / n)項(xiàng)工作。我很樂意為任何能夠?qū)⑽业膯l(fā)式方法轉(zhuǎn)化為最壞情況不可能比這更糟糕的證據(jù)的人辯護(hù)。