九章演算法 | Google面試題：目標和

01-26

撰文 | JZ

專欄 | 九章演算法

題目描述

現有一個非負整數列a1, a2, ..., an和一個期望值S。你可以為每一個整數賦一個新符號，符號從+ 和-兩種符號中選擇。計算出有多少種組合可以令賦予符號後的這些整數的和等於S。

樣例

輸入：數列nums=[1,1,1,1,1]，S=3

輸出：5

解釋：有5種可令這些整數賦予新符號後和為期望值3的組合。

-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3

數據範圍

1.數組長度為正數並不超過20

2.數組中所有整數的和不超過1000

3.輸出的答案不會超過32位整數（2,147,483,647）

解題思路

DFS解法：

解這道題最直白的思路就是直接搜索，窮舉每一種情況。但是可以看到這種搜索的時間複雜度到達O(2^n)，是不可取的指數級。我們思考有沒有辦法可以「剪枝」，也就是在搜索到最後一個數之前就判斷這條路是否可行。若不可行則直接return，減少遞歸次數。

因為數列被限定均為非負整數，所以全賦+號和全賦-號分別是這個數列能組合得到的最大值和最小值。我們不妨將全賦+號得到的和記為sum，那麼需要有-sum<=S<=sum，否則肯定是沒有辦法用數列中的數組成S的，答案便是0。

這個邊界判斷還是比較容易想到的，套用這個思路，在搜索的過程中，如果當前搜索過的數字的和加上右邊所有還沒有被搜索到的數還小於S，或者減去右邊所有的數還大於S，那自然這條路是走不通的，可以被剪枝。

從編程的角度考慮，我們可以建立一個數組s，s[i]代表數列中第i個數右邊所有數的和。這個數組的建立只需要從後至前掃描原數列，需要O(n)時間。搜索過程中我們每一次搜索都要進行上述的比對，進行剪枝。

這樣剪枝的話，如果期望值S是一個比較大的正數（越接近sum優化效果越好），那麼向負號方向的搜索就會比較快的被終止。如果期望值是一個負數是同理的。依據上述分析，對於大多數數據，這個剪枝還是有較好的優化效果的，但對於某些極端數據優化效果較差。

DP解法：

DFS解法即使經過優化，時間複雜度的級別還是下不來。我們觀察這個問題能不能通過解決子問題來求解，從而用DP的思路求解。我們先去掉數列中的最後一個數，考慮能不能用前n-1個數的計算結果來推出所有n個數的計算結果。

我們用dp[n-1,e]來表示數列中只有n-1個數、題目期望值為e時輸出的答案。那麼我們真正需要的答案用這個方法表示自然就是dp[n,S]了。因為第n個數的符號非正即負只有兩種狀態，所以dp[n,S]=dp[n-1,S-an]+dp[n-1,S+an]。這個方程還是比較容易想到的。用樣例來說明，第五個數為1，那麼只有前四個數和為4（第五個數符號為+）或者6（第五個數符號為-）的時候可以得到期望值。即我們需要的就是前4個數有多少種組合可以令和為4或者為6的，並讓他們相加。

隨著我們的思路，不僅我們成功地將問題分解為了子問題，順帶連狀態轉移方程也一同得到了。那麼我們用兩層循環即可完成這個DP。DP的初始狀態為只有一個數的時候，我們讓dp[1,a1]和dp[1,-a1]均為1即可（額外注意當a1=0時為特殊情況，應令dp[1,0]=2）。

這裡我們就發現了一個問題，我們剛剛思路中用的dp的第二個下標是可以為負數的，範圍為[-sum,sum]（排除掉S>sum和S<-sum這兩種已知無解的情況）。然而我們程序中數組的下標是從0開始的，所以我們把這個下標的值都加上一個sum，讓它的範圍變成[0,2*sum]，方便我們編程。此外記得注意數組下標的邊界檢查。

參考代碼

面試官角度分析

雖然看到這道題後，搜索是一個比較自然的思路，但是即使是優化過後的時間複雜度也依然處於指數級，所以動態規劃解法是這道題一個較好的解法，面試時應快速對兩種演算法進行權衡。但是這道題搜索的優化方法並不止本文提供的這一種，能提出良好的搜索優化方案也能展現給面試官你良好的邏輯思路。