網際網路公司高頻面試題目「回溯算法」：求組合總和II

這篇可以說是全網把組合問題如何去重，講得最清晰的了！

通知：我將公眾號文章和學習相關的資料整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在電腦上學習，可以fork到自己倉庫，順便也給個star支持一波吧！

40.組合總和II

題目連結：https://leetcode-cn.com/problems/combination-sum-ii/

給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中只能使用一次。

說明：
所有數字（包括目標數）都是正整數。
解集不能包含重複的組合。

示例 1:
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集為:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
輸入: candidates = [2,5,2,1,2], target = 5,
所求解集為:
[
[1,2,2],
[5]
]

思路

這道題目和如下區別：

1. 本題candidates 中的每個數字在每個組合中只能使用一次。
2. 本題數組candidates的元素是有重複的，而是無重複元素的數組candidates

最後本題和要求一樣，解集不能包含重複的組合。

「本題的難點在於區別2中：集合（數組candidates）有重複元素，但還不能有重複的組合」。

一些同學可能想了：我把所有組合求出來，再用set或者map去重，這麼做很容易超時！

所以要在搜索的過程中就去掉重複組合。

很多同學在去重的問題上想不明白，其實很多題解也沒有講清楚，反正代碼是能過的，感覺是那麼回事，稀裡糊塗的先把題目過了。

這個去重為什麼很難理解呢，「所謂去重，其實就是使用過的元素不能重複選取。」 這麼一說好像很簡單！

都知道組合問題可以抽象為樹形結構，那麼「使用過」在這個樹形結構上是有兩個維度的，一個維度是同一樹枝上使用過，一個維度是同一樹層上使用過。「沒有理解這兩個層面上的「使用過」 是造成大家沒有徹底理解去重的根本原因。」

那麼問題來了，我們是要同一樹層上使用過，還是統一樹枝上使用過呢？

回看一下題目，元素在同一個組合內是可以重複的，怎麼重複都沒事，但兩個組合不能相同。

「所以我們要去重的是同一樹層上的「使用過」，同一樹枝上的都是一個組合裡的元素，不用去重」。

為了理解去重我們來舉一個例子，candidates = [1, 1, 2], target = 3，（方便起見candidates已經排序了）

選擇過程樹形結構如圖所示：

可以看到圖中，每個節點相對於我多加了used數組，這個used數組下面會重點介紹。

回溯三部曲

• 「遞歸函數參數」

與套路相同，此題還需要加一個bool型數組used，用來記錄同一樹枝上的元素是否使用過。

這個集合去重的重任就是used來完成的。

代碼如下：

vector<vector<int>> result; // 存放組合集合vector<int> path;           // 符合條件的組合void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {

• 「遞歸終止條件」

與相同，終止條件為 sum > target 和 sum == target。

代碼如下：

if (sum > target) { // 這個條件其實可以省略     return;}if (sum == target) {    result.push_back(path);    return;}

sum > target 這個條件其實可以省略，因為和在遞歸單層遍歷的時候，會有剪枝的操作，下面會介紹到。

• 「單層搜索的邏輯」

這裡與最大的不同就是要去重了。

前面我們提到：要去重的是「同一樹層上的使用過」，如果判斷同一樹層上元素（相同的元素）是否使用過了呢。

「如果candidates[i] == candidates[i - 1] 並且 used[i - 1] == false，就說明：前一個樹枝，使用了candidates[i - 1]，也就是說同一樹層使用過candidates[i - 1]」。

此時for循環裡就應該做continue的操作。

這塊比較抽象，如圖：

我在圖中將used的變化用橘黃色標註上，可以看出在candidates[i] == candidates[i - 1]相同的情況下：

• used[i - 1] == true，說明同一樹支candidates[i - 1]使用過
• used[i - 1] == false，說明同一樹層candidates[i - 1]使用過

「這塊去重的邏輯很抽象，網上搜的題解基本沒有能講清楚的，如果大家之前思考過這個問題或者刷過這道題目，看到這裡一定會感覺通透了很多！」

那麼單層搜索的邏輯代碼如下：

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {    // used[i - 1] == true，說明同一樹支candidates[i - 1]使用過    // used[i - 1] == false，說明同一樹層candidates[i - 1]使用過    // 要對同一樹層使用過的元素進行跳過    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {        continue;    }    sum += candidates[i];    path.push_back(candidates[i]);    used[i] = true;    backtracking(candidates, target, sum, i + 1, used); // 和39.組合總和的區別1：這裡是i+1，每個數字在每個組合中只能使用一次    used[i] = false;    sum -= candidates[i];    path.pop_back();}

「注意sum + candidates[i] <= target為剪枝操作，在有講解過！」

C++代碼

回溯三部曲分析完了，整體C++代碼如下：

class Solution {private:    vector<vector<int>> result;    vector<int> path;    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {        if (sum == target) {            result.push_back(path);            return;        }        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {            // used[i - 1] == true，說明同一樹支candidates[i - 1]使用過            // used[i - 1] == false，說明同一樹層candidates[i - 1]使用過            // 要對同一樹層使用過的元素進行跳過            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {                continue;            }            sum += candidates[i];            path.push_back(candidates[i]);            used[i] = true;            backtracking(candidates, target, sum, i + 1, used); // 和39.組合總和的區別1，這裡是i+1，每個數字在每個組合中只能使用一次            used[i] = false;            sum -= candidates[i];            path.pop_back();        }    }public:    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {        vector<bool> used(candidates.size(), false);        path.clear();        result.clear();        // 首先把給candidates排序，讓其相同的元素都挨在一起。        sort(candidates.begin(), candidates.end());        backtracking(candidates, target, 0, 0, used);        return result;    }};

總結

本題同樣是求組合總和，但就是因為其數組candidates有重複元素，而要求不能有重複的組合，所以相對於難度提升了不少。

「關鍵是去重的邏輯，代碼很簡單，網上一搜一大把，但幾乎沒有能把這塊代碼含義講明白的，基本都是給出代碼，然後說這就是去重了，究竟怎麼個去重法也是模稜兩可」。

所以Carl有必要把去重的這塊徹徹底底地給大家講清楚，「就連「樹層去重「和「樹枝去重」都是我自創的詞彙，希望對大家理解有幫助！」

就醬，如果感覺「代碼隨想錄」誠意滿滿，就幫Carl宣傳一波吧，感謝啦！

我是程式設計師Carl，個人主頁：https://github.com/youngyangyang04

這裡每天8:35準時推送一道經典算法題目，我選擇的每道題目都不是孤立的，而是由淺入深，環環相扣，幫你梳理算法知識脈絡，輕鬆學算法！

期待你的關注