設計一個算法來檢查給定集合中是否有k個整數加起來得到x

給定一組n個整數和一個整數x。你能設計一個算法來檢查給定集合中的k個整數是否加起來爲x？的複雜性應爲O（n ^（K-1）* logn）時間設計一個算法來檢查給定集合中是否有k個整數加起來得到x

2012-01-27 user973931

問題通常在其中至少有一個問號。 – 2012-01-27 23:18:34

@TimCooper - 他們很匆忙，他們正在接受採訪，現在在iPhone上發佈這個消息！ – 2012-01-27 23:23:33

嘗試使用'Array'的'排列'功能。 – itdoesntwork 2012-01-27 23:23:54

最終複雜性：爲O（n ^（K-1）* logn）時間

如果您有足夠的空間（n ^（k/2）長度），您也可以在O（n ^（k/2）log（n）陣列。

計算總和爲O（1），因爲您可以重新使用您爲上一個組合進行的計算。如果已經計算（a + b + c + d），（a + b + c + e）=（a + b + c + d）-d + e。

2012-01-27 23:35:56 ElKamina

我們如何找到'總和（組合）'？那麼把'O（n）'的複雜度提高到'O（n ^（k-1）* n）'是不是會花費呢？另外，我相信在步驟2中，你的意思是「...... k-1號......」。 – quasiverse 2012-01-27 23:47:09

最後，你確定有'n ^（k-1）'組合嗎？我相信有選擇他們中的k，我不明白他們是如何平等的。 – quasiverse 2012-01-27 23:53:25

@quasiverse ... nCk-1是 user973931 2012-01-28 00:16:09

回答