Leetcode 1982 Find Array Given Subset Sums

 Leetcode 1982 Find Array Given Subset Sums

    github

這題是從子集合還原成原數組, 

提供的集合是所有數組的各集合加總. 

例如若原數組 是 {1, 2, 3} 三個數 , n = 3,

各子集合排列組合為 {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

則提供的 sums 為 {0, 1, 2, 3, 3, 4, 5, 6}

這題有人說是數學題, 而非程式題. 

的確沒找到好方法的話, 是過不了這一題的. 時間會超過. 

這也正體現有好的演算法, 和沒有的在執行上會有巨大的差距. 

 雖然 wintel 政策是發展硬體做快速的 CPU 運算 

和 更大的記憶體儲存. 

但有好的演算法可更加地來利用硬體資源.

方式有很多, 介紹其中一種分析 - 討論 

我們先把數列排序後來分析: 

{s0, s1, s2, ..., sn}

s1 = s0 + d

拆成

S0: {s0, ... si}

S1: {s0 + d, ... si + d}

並保證空集合{} 的總和 0 , 在處理時, 一直存在數列中.

--

假如 d/-d 不在數組中的話, 因為 s0 / s1 都是數組的組合

    

   (1) 如果 s0 == 0 , s1 = d, 矛盾

   (2) 如果 s0 < 0:

        如果 s1 > 0, 0 不見了, 矛盾

        如果 s1 == 0, s0 = -d, 矛盾

        如果 s1 < 0, 表示有其他的 負數 k 不在 s0 中, 則 s0 + k  會比 s0 還小

   (3) 如果 s0 > 0, 0 不見了, 矛盾

而因為 S1: {s0 + d, ... si + d}

下一回sums[1], sums[0]兩個相減時, 

S1 數列裡的數字 d 的因素就會被消除. 

--

例如, 若有個數列 [-355,0,10,44,365,399,409,764]

一開始先用 sums[1] - sums[0] 得到 d = 355

接著可以得到兩群,  是 {Si + 355, ... } 和 與 355 無關的. 

因為這數列是排序過的. 所以 sums[1] >= sums[0], d >= 0

若 sums[i] = sums[j] + d , d >= 0 則 sums[i] >= sums[j]

所以我們可以從數列一開始檢查起. 

     0 = -355 + 355

     365 = 10 + 355

     399 = 44 + 355

     764 = 409 + 355

如果是 +355 後可以找到的, 就放在 S1. 

其他的包含 sums[0] 就放在 S0

會得到 S0 : {-365, 10, 44, 409} 和 S1 {0, 365, 399, 764} 兩個

而這個 d 值, 

1. 如果 原數組有負數時, x + d = 0

   表示 0 會在 S1, 這時 d 取負值

2. 反之 0 會在 S0, 這時 d 取正值. 

於是得到 

     -365, S1 {0,365, 399, 764}

    365, S0 {0, 399}

    399 

程式: