題目: 2386. Find the K-Sum of an Array
難度: Hard
目前下列解法的時間複雜度: O(n*k) - ?(依資料值而定)
題目說明
從一整數陣列中取出一些數字後，加起來，可以得到一個值。
求所有組合中，第k大的數字和為多少。
(取不同位置的相同數字之組合視為不同組合。)
解法：鑽題目範圍漏洞、dp、剪枝
鑽題目範圍漏洞：
題目最後跟你說k不會超過2000。
dp：
所有組合其實就是每個數字取或不取，組合數 = 2 的 n 次方。
假設你現在有在 i 位置之前的「所有數字組合和」所構成的陣列 arr_i-1 ，此時再加入位於 i 位置的數字 n_i ，則新的「所有數字組合和」所構成的陣列：
arr_i = (arr_i-1中每個元素加上n_i) + arr_i-1
注意到加法只會對陣列中的數字造成位移，不會改變陣列中數字的大小關係。因此，原本其結果就已經不是前 k 大的數字，依然不會成為前 k 大；反而因為位移不夠大，原本是前 k 大的數字有可能被擠出前 k 大。
利用這點，只要在原本的 arr_i-1 與新的 arr_i 之間保留前 k 大的數字就好了。
沒選數字的和為 0 ，即 arr_-1 = [0] 。
然後你還是會 TLE 。於是就出動最後一步：剪枝。
如果新的數字比原陣列的「最小 - 最大」還要小，那麼新增加的數字必不是前 k 大，故可以直接「略過新數字」。
如果新的數字比原陣列的「最大 - 最小」還要大，那麼新增加的數字必是前 k 大，故可以直接「捨棄原陣列」的所有數字。
而要做得快就是直接把指標指過去；要加進去的話直接加到另一個變數上， return 時再補上就好。
source code
好耶，記憶體比 100% 的人用得還要少。
啊這個分布是發生什麼事了？
是因為我用Cㄇ?
難度: Hard
目前下列解法的時間複雜度: O(n*k) - ?(依資料值而定)
題目說明
從一整數陣列中取出一些數字後，加起來，可以得到一個值。
求所有組合中，第k大的數字和為多少。
(取不同位置的相同數字之組合視為不同組合。)
解法：鑽題目範圍漏洞、dp、剪枝
鑽題目範圍漏洞：
題目最後跟你說k不會超過2000。
dp：
所有組合其實就是每個數字取或不取，組合數 = 2 的 n 次方。
假設你現在有在 i 位置之前的「所有數字組合和」所構成的陣列 arr_i-1 ，此時再加入位於 i 位置的數字 n_i ，則新的「所有數字組合和」所構成的陣列：
arr_i = (arr_i-1中每個元素加上n_i) + arr_i-1
注意到加法只會對陣列中的數字造成位移，不會改變陣列中數字的大小關係。因此，原本其結果就已經不是前 k 大的數字，依然不會成為前 k 大；反而因為位移不夠大，原本是前 k 大的數字有可能被擠出前 k 大。
利用這點，只要在原本的 arr_i-1 與新的 arr_i 之間保留前 k 大的數字就好了。
沒選數字的和為 0 ，即 arr_-1 = [0] 。
然後你還是會 TLE 。於是就出動最後一步：剪枝。
如果新的數字比原陣列的「最小 - 最大」還要小，那麼新增加的數字必不是前 k 大，故可以直接「略過新數字」。
如果新的數字比原陣列的「最大 - 最小」還要大，那麼新增加的數字必是前 k 大，故可以直接「捨棄原陣列」的所有數字。
而要做得快就是直接把指標指過去；要加進去的話直接加到另一個變數上， return 時再補上就好。
source code
好耶，記憶體比 100% 的人用得還要少。
