之前說(shuō)過(guò)回溯算法是筆試中最好用的算法，只要你沒(méi)什么思路，就用回溯算法暴力求解，即便不能通過(guò)所有測(cè)試用例，多少能過(guò)一點(diǎn)。

回溯算法的技巧也不難，前文 回溯算法框架套路 說(shuō)過(guò)，回溯算法就是窮舉一棵決策樹(shù)的過(guò)程，只要在遞歸之前「做選擇」，在遞歸之后「撤銷選擇」就行了。

但是，就算暴力窮舉，不同的思路也有優(yōu)劣之分。

本文就來(lái)看一道非常經(jīng)典的回溯算法問(wèn)題，子集劃分問(wèn)題，可以幫你更深刻理解回溯算法的思維，得心應(yīng)手地寫(xiě)出回溯函數(shù)。

題目非常簡(jiǎn)單：

給你輸入一個(gè)數(shù)組nums和一個(gè)正整數(shù)k，請(qǐng)你判斷nums是否能夠被平分為元素和相同的k個(gè)子集。

函數(shù)簽名如下：

boolean canPartitionKSubsets（int［］ nums， int k）;

我們之前 背包問(wèn)題之子集劃分 寫(xiě)過(guò)一次子集劃分問(wèn)題，不過(guò)那道題只需要我們把集合劃分成兩個(gè)相等的集合，可以轉(zhuǎn)化成背包問(wèn)題用動(dòng)態(tài)規(guī)劃技巧解決。

但是如果劃分成多個(gè)相等的集合，解法一般只能通過(guò)暴力窮舉，時(shí)間復(fù)雜度爆表，是練習(xí)回溯算法和遞歸思維的好機(jī)會(huì)。

一、思路分析

把裝有n個(gè)數(shù)字的數(shù)組nums分成k個(gè)和相同的集合，你可以想象將n個(gè)數(shù)字分配到k個(gè)「桶」里，最后這k個(gè)「桶」里的數(shù)字之和要相同。

前文 回溯算法框架套路 說(shuō)過(guò)，回溯算法的關(guān)鍵在哪里？

關(guān)鍵是要知道怎么「做選擇」，這樣才能利用遞歸函數(shù)進(jìn)行窮舉。

那么回想我們這個(gè)問(wèn)題，將n個(gè)數(shù)字分配到k個(gè)桶里，我們可以有兩種視角：

視角一，如果我們切換到這n個(gè)數(shù)字的視角，每個(gè)數(shù)字都要選擇進(jìn)入到k個(gè)桶中的某一個(gè)。

視角二，如果我們切換到這k個(gè)桶的視角，對(duì)于每個(gè)桶，都要遍歷nums中的n個(gè)數(shù)字，然后選擇是否將當(dāng)前遍歷到的數(shù)字裝進(jìn)自己這個(gè)桶里。

你可能問(wèn)，這兩種視角有什么不同？

用不同的視角進(jìn)行窮舉，雖然結(jié)果相同，但是解法代碼的邏輯完全不同；對(duì)比不同的窮舉視角，可以幫你更深刻地理解回溯算法，我們慢慢道來(lái)。

二、以數(shù)字的視角

用 for 循環(huán)迭代遍歷nums數(shù)組大家肯定都會(huì)：

for （int index = 0; index 《 nums.length; index++） {

System.out.println（nums［index］）;

}

遞歸遍歷數(shù)組你會(huì)不會(huì)？其實(shí)也很簡(jiǎn)單：

void traverse（int［］ nums， int index） {

if （index == nums.length） {

return;

}

System.out.println（nums［index］）;

traverse（nums， index + 1）;

}

只要調(diào)用traverse（nums， 0），和 for 循環(huán)的效果是完全一樣的。

那么回到這道題，以數(shù)字的視角，選擇k個(gè)桶，用 for 循環(huán)寫(xiě)出來(lái)是下面這樣：

// k 個(gè)桶（集合），記錄每個(gè)桶裝的數(shù)字之和

int［］ bucket = new int［k］;

// 窮舉 nums 中的每個(gè)數(shù)字

for （int index = 0; index 《 nums.length; index++） {

// 窮舉每個(gè)桶

for （int i = 0; i 《 k; i++） {

// nums［index］ 選擇是否要進(jìn)入第 i 個(gè)桶

// 。..

}

}

如果改成遞歸的形式，就是下面這段代碼邏輯：

// k 個(gè)桶（集合），記錄每個(gè)桶裝的數(shù)字之和

int［］ bucket = new int［k］;

// 窮舉 nums 中的每個(gè)數(shù)字

void backtrack（int［］ nums， int index） {

// base case

if （index == nums.length） {

return;

}

// 窮舉每個(gè)桶

for （int i = 0; i 《 bucket.length; i++） {

// 選擇裝進(jìn)第 i 個(gè)桶

bucket［i］ += nums［index］;

// 遞歸窮舉下一個(gè)數(shù)字的選擇

backtrack（nums， index + 1）;

// 撤銷選擇

bucket［i］ -= nums［index］;

}

}

雖然上述代碼僅僅是窮舉邏輯，還不能解決我們的問(wèn)題，但是只要略加完善即可：

// 主函數(shù)

public boolean canPartitionKSubsets（int［］ nums， int k） {

// 排除一些基本情況

if （k 》 nums.length） return false;

int sum = 0;

for （int v ： nums） sum += v;

if （sum % k ！= 0） return false;

// k 個(gè)桶（集合），記錄每個(gè)桶裝的數(shù)字之和

int［］ bucket = new int［k］;

// 理論上每個(gè)桶（集合）中數(shù)字的和

int target = sum / k;

// 窮舉，看看 nums 是否能劃分成 k 個(gè)和為 target 的子集

return backtrack（nums， 0， bucket， target）;

}

// 遞歸窮舉 nums 中的每個(gè)數(shù)字

boolean backtrack（

int［］ nums， int index， int［］ bucket， int target） {

if （index == nums.length） {

// 檢查所有桶的數(shù)字之和是否都是 target

for （int i = 0; i 《 bucket.length; i++） {

if （bucket［i］ ！= target） {

return false;

}

}

// nums 成功平分成 k 個(gè)子集

return true;

}

// 窮舉 nums［index］ 可能裝入的桶

for （int i = 0; i 《 bucket.length; i++） {

// 剪枝，桶裝裝滿了

if （bucket［i］ + nums［index］ 》 target） {

continue;

}

// 將 nums［index］ 裝入 bucket［i］

bucket［i］ += nums［index］;

// 遞歸窮舉下一個(gè)數(shù)字的選擇

if （backtrack（nums， index + 1， bucket， target）） {

return true;

}

// 撤銷選擇

bucket［i］ -= nums［index］;

}

// nums［index］ 裝入哪個(gè)桶都不行

return false;

}

有之前的鋪墊，相信這段代碼是比較容易理解的。這個(gè)解法雖然能夠通過(guò)，但是耗時(shí)比較多，其實(shí)我們可以再做一個(gè)優(yōu)化。

主要看backtrack函數(shù)的遞歸部分：

for （int i = 0; i 《 bucket.length; i++） {

// 剪枝

if （bucket［i］ + nums［index］ 》 target） {

continue;

}

if （backtrack（nums， index + 1， bucket， target）） {

return true;

}

}

如果我們讓盡可能多的情況命中剪枝的那個(gè) if 分支，就可以減少遞歸調(diào)用的次數(shù)，一定程度上減少時(shí)間復(fù)雜度。

如何盡可能多的命中這個(gè) if 分支呢？要知道我們的index參數(shù)是從 0 開(kāi)始遞增的，也就是遞歸地從 0 開(kāi)始遍歷nums數(shù)組。

如果我們提前對(duì)nums數(shù)組排序，把大的數(shù)字排在前面，那么大的數(shù)字會(huì)先被分配到bucket中，對(duì)于之后的數(shù)字，bucket［i］ + nums［index］會(huì)更大，更容易觸發(fā)剪枝的 if 條件。

所以可以在之前的代碼中再添加一些代碼：

public boolean canPartitionKSubsets（int［］ nums， int k） {

// 其他代碼不變

// 。..

/* 降序排序 nums 數(shù)組 */

Arrays.sort（nums）;

int i = 0， j = nums.length - 1;

for （; i 《 j; i++， j--） {

// 交換 nums［i］ 和 nums［j］

int temp = nums［i］;

nums［i］ = nums［j］;

nums［j］ = temp;

}

/*******************/

return backtrack（nums， 0， bucket， target）;

}

由于 Java 的語(yǔ)言特性，這段代碼通過(guò)先升序排序再反轉(zhuǎn)，達(dá)到降序排列的目的。

三、以桶的視角

文章開(kāi)頭說(shuō)了，以桶的視角進(jìn)行窮舉，每個(gè)桶需要遍歷nums中的所有數(shù)字，決定是否把當(dāng)前數(shù)字裝進(jìn)桶中；當(dāng)裝滿一個(gè)桶之后，還要裝下一個(gè)桶，直到所有桶都裝滿為止。

這個(gè)思路可以用下面這段代碼表示出來(lái)：

// 裝滿所有桶為止

while （k 》 0） {

// 記錄當(dāng)前桶中的數(shù)字之和

int bucket = 0;

for （int i = 0; i 《 nums.length; i++） {

// 決定是否將 nums［i］ 放入當(dāng)前桶中

bucket += nums［i］ or 0;

if （bucket == target） {

// 裝滿了一個(gè)桶，裝下一個(gè)桶

k--;

break;

}

}

}

那么我們也可以把這個(gè) while 循環(huán)改寫(xiě)成遞歸函數(shù)，不過(guò)比剛才略微復(fù)雜一些，首先寫(xiě)一個(gè)backtrack遞歸函數(shù)出來(lái)：

boolean backtrack（int k， int bucket，

int［］ nums， int start， boolean［］ used， int target）;

不要被這么多參數(shù)嚇到，我會(huì)一個(gè)個(gè)解釋這些參數(shù)。如果你能夠透徹理解本文，也能得心應(yīng)手地寫(xiě)出這樣的回溯函數(shù)。

這個(gè)backtrack函數(shù)的參數(shù)可以這樣解釋：

現(xiàn)在k號(hào)桶正在思考是否應(yīng)該把nums［start］這個(gè)元素裝進(jìn)來(lái)；目前k號(hào)桶里面已經(jīng)裝的數(shù)字之和為bucket；used標(biāo)志某一個(gè)元素是否已經(jīng)被裝到桶中；target是每個(gè)桶需要達(dá)成的目標(biāo)和。

根據(jù)這個(gè)函數(shù)定義，可以這樣調(diào)用backtrack函數(shù)：

public boolean canPartitionKSubsets（int［］ nums， int k） {

// 排除一些基本情況

if （k 》 nums.length） return false;

int sum = 0;

for （int v ： nums） sum += v;

if （sum % k ！= 0） return false;

boolean［］ used = new boolean［nums.length］;

int target = sum / k;

// k 號(hào)桶初始什么都沒(méi)裝，從 nums［0］ 開(kāi)始做選擇

return backtrack（k， 0， nums， 0， used， target）;

}

實(shí)現(xiàn)backtrack函數(shù)的邏輯之前，再重復(fù)一遍，從桶的視角：

1、需要遍歷nums中所有數(shù)字，決定哪些數(shù)字需要裝到當(dāng)前桶中。

2、如果當(dāng)前桶裝滿了（桶內(nèi)數(shù)字和達(dá)到target），則讓下一個(gè)桶開(kāi)始執(zhí)行第 1 步。

下面的代碼就實(shí)現(xiàn)了這個(gè)邏輯：

boolean backtrack（int k， int bucket，

int［］ nums， int start， boolean［］ used， int target） {

// base case

if （k == 0） {

// 所有桶都被裝滿了，而且 nums 一定全部用完了

// 因?yàn)?target == sum / k

return true;

}

if （bucket == target） {

// 裝滿了當(dāng)前桶，遞歸窮舉下一個(gè)桶的選擇

// 讓下一個(gè)桶從 nums［0］ 開(kāi)始選數(shù)字

return backtrack（k - 1， 0 ，nums， 0， used， target）;

}

// 從 start 開(kāi)始向后探查有效的 nums［i］ 裝入當(dāng)前桶

for （int i = start; i 《 nums.length; i++） {

// 剪枝

if （used［i］） {

// nums［i］ 已經(jīng)被裝入別的桶中

continue;

}

if （nums［i］ + bucket 》 target） {

// 當(dāng)前桶裝不下 nums［i］

continue;

}

// 做選擇，將 nums［i］ 裝入當(dāng)前桶中

used［i］ = true;

bucket += nums［i］;

// 遞歸窮舉下一個(gè)數(shù)字是否裝入當(dāng)前桶

if （backtrack（k， bucket， nums， i + 1， used， target）） {

return true;

}

// 撤銷選擇

used［i］ = false;

bucket -= nums［i］;

}

// 窮舉了所有數(shù)字，都無(wú)法裝滿當(dāng)前桶

return false;

}

至此，這道題的第二種思路也完成了。

四、最后總結(jié)

本文寫(xiě)的這兩種思路都可以通過(guò)所有測(cè)試用例，不過(guò)第一種解法即便經(jīng)過(guò)了排序優(yōu)化，也明顯比第二種解法慢很多，這是為什么呢？

我們來(lái)分析一下這兩個(gè)算法的時(shí)間復(fù)雜度，假設(shè)nums中的元素個(gè)數(shù)為n。

先說(shuō)第一個(gè)解法，也就是從數(shù)字的角度進(jìn)行窮舉，n個(gè)數(shù)字，每個(gè)數(shù)字有k個(gè)桶可供選擇，所以組合出的結(jié)果個(gè)數(shù)為k^n，時(shí)間復(fù)雜度也就是O（k^n）。

第二個(gè)解法，每個(gè)桶要遍歷n個(gè)數(shù)字，選擇「裝入」或「不裝入」，組合的結(jié)果有2^n種；而我們有k個(gè)桶，所以總的時(shí)間復(fù)雜度為O（k*2^n）。

當(dāng)然，這是理論上的最壞復(fù)雜度，實(shí)際的復(fù)雜度肯定要好一些，畢竟我們添加了這么多剪枝邏輯。不過(guò)，從復(fù)雜度的上界已經(jīng)可以看出第一種思路要慢很多了。

所以，誰(shuí)說(shuō)回溯算法沒(méi)有技巧性的？雖然回溯算法就是暴力窮舉，但窮舉也分聰明的窮舉方式和低效的窮舉方式，關(guān)鍵看你以誰(shuí)的「視角」進(jìn)行窮舉。

通俗來(lái)說(shuō)，我們應(yīng)該盡量「少量多次」，就是說(shuō)寧可多做幾次選擇，也不要給太大的選擇空間；寧可「二選一」選k次，也不要 「k選一」選一次。

這道題我們從兩種視角進(jìn)行窮舉，雖然代碼量看起來(lái)多，但核心邏輯都是類似的，相信你通過(guò)本文能夠更深刻地理解回溯算法。
編輯：lyn