九章演算法 | Ebay 面試題 : 把數組分成和大小一樣的集合

撰文 | JZ

專欄 | 九章演算法

題目描述

給定一個只包含正整數的非空數組，判斷該數組能否分成兩個和相等的子數組。

樣例輸入

輸入[1,5,11,5] 返回 true . 可以分為[1,5,5]和[11]

演算法分析

本題需要判斷數組能否分為兩個和想等的子數組，等價於在數組中選取一定數目的元素，能否使得選擇的元素之和為sum/2(sum為數組中所有元素的和)。而等價的問題就是經典的0-1背包問題，即給定一個正整數數組，能否從數組中選取一定數量的元素，使得這些元素的和恰好為sum/2。

為了解決這個問題，直觀的想法是我們可以枚舉原數組的所有子集，計算每個子集的元素之和能否等於sum/2,但是含有n個元素的數組的子集數目為2^n個，這樣演算法的複雜度是指數級別的，在n比較大的時候並不可行。

我們假設數組中存在子集num1,num2,...,numk滿足和為sum/2,那麼，從該子集中去掉最後一個元素numk,其和一定為sum/2-numk。也就是說子問題：是否存在一個子集，其和為sum/2-numk,該問題一定是有解的（可以用反證法證明）。

這樣，我們可以確定，原問題有解當且僅當子問題有解。這樣，我們就把一個規模比較大的問題歸結成了規模比較小的子問題。這就是動態規劃的思想。那麼，我們如何確定子問題是否有解呢？可以這樣考慮，假設dp[i][j]表示數組中前i個元素能否得到和為j的子數組，dp[i][j] = 1表示前i個元素能夠得到和為j的子數組，dp[i][j] = 0 表示不能得到。那麼對於第i個元素來說，有兩種情況，一種是第i個元素在和為j的子數組中，那麼對於前i-1個元素來講，應該得到和為j-nums[i]的子數組；另一種情況是第i個元素不在和為j的子數組中，那麼對於前i-1個元素來講，應該得到和為j的子數組。上述兩種情況成立其一就可以保證能夠得到合法解。因此我們有以下關係：

dp[i][j] = dp[i-1][j] | dp[i-1]][j-nums[i]]

上述解法的時間複雜度和空間複雜度均為O（n*sum）的，由於問題中，n*sum = 200 * 100 * 200 = 4*10^6,我們x需要優化空間複雜度。進一步思考我們發現，第i次迭代的過程只與第i-1次迭代過程有關係，而與前i-2次迭代過程無關。因此我我們首先可以考慮使用2×sum的滾動數組來解決此題。此時可以把空間複雜度壓縮到O(sum)。

另一種解法是一維動態規劃，我們假設dp[j]表示第i輪迭代能否得到和為j的子數組，那麼只要保證此時數組中存儲的是上一輪（i-1輪）迭代的結果，我們就可以去掉一個維度。因此我們有如下關係：

dp[j] = dp[j] | dp[j - nums[i]]

但是這種情況下，內層循環必須從大往小循環（請讀者思考為什麼）。

下面給出O(sum)空間複雜度的一維動態規劃解法。

參考代碼

面試官角度分析

本題是動態規劃的經典問題0-1背包的簡單變形，給出動態規劃演算法可以達到hire的程度。

LintCode相關練習題

http://www.lintcode.com/zh-cn/problem/backpack-i/

http://www.lintcode.com/zh-cn/problem/backpack-ii/

http://www.lintcode.com/zh-cn/problem/backpack-iii/

http://www.lintcode.com/zh-cn/problem/backpack-vi/

http://www.lintcode.com/zh-cn/problem/backpack-v/