Leecode 39. 組合總和

題目描述

給你一個 無重復元素 的整數數組 candidates 和一個目標整數 target ，找出 candidates 中可以使數字和為目標數 target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。

candidates 中的 同一個 數字可以 無限制重復被選取 。如果至少一個數字的被選數量不同，則兩種組合是不同的。

對于給定的輸入，保證和為 target 的不同組合數少于 150 個。

• 示例 1：

輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個候選， 7 = 7 。
僅有這兩種組合。

• 示例 2：

輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]

• 示例 3：

輸入: candidates = [2], target = 1
輸出: []

第一次錯誤嘗試的思路

本題的一上來的思路并不算難，同時記錄當前數組與當前數組的和作為當前狀態，在遞歸函數中使用for循環來遍歷所有下一個狀態，并在遞歸后進行恢復回溯。主要難點就在于要確保不會重復。首先對于去重我想到的是使用set集合容器，將結果數組存放入集合中，就可以刪去重復項。但此時又會遇到，當存入的vector中數相同但順序不同時也算集合中的不同元素。因此為了解決這個問題我又在滿足條件時的判斷中加了一條對每一次符合條件的vector進行一次快排，得到代碼如下：

class Solution {
public:
    void combHelper(vector<int>& candidates, set<vector<int>>& vecSet, vector<int>& curVec, int& curSum, int target){
        if(curSum == target){
            sort(curVec.begin(), curVec.end()); // 使用sort對vector排序，確保存入的vector不會有重復
            vecSet.insert(curVec); // 用set來存放結果，避免重復
            return;
        }
        if(curSum > target) return; // 如果當前和大于目標值，則直接返回

        for(int i = 0; i < candidates.size(); i++){
            curVec.push_back(candidates[i]); // 存入下一狀態的值
            curSum += candidates[i]; // 更新下一狀態的和
            combHelper(candidates, vecSet, curVec, curSum, target); // 遞歸下一狀態
            curSum -= candidates[i];  // 回溯，恢復數組和
            curVec.pop_back(); // 回溯，恢復數組
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        set<vector<int>> vecSet; // 使用set來存放結果，避免重復
        vector<int> curVec; // 初始化初始數組，初始數組和
        int curSum = 0;

        combHelper(candidates, vecSet, curVec, curSum, target); // 遞歸調用查找所有符合條件的值

        vector<vector<int>> result(vecSet.begin(), vecSet.end()); // 將set轉換為vec結果
        return result; // 返回
    }
};

上面這段代碼乍一看感覺沒什么問題，但是實際上運行時會有一些測試用例無法通過，例如：

輸入：candidates = [2,3,5]，target = 8
輸出：[[2,2,2,2],[2,2,3],[2,3,3],[2,5],[3,5]]
預期結果：[[2,2,2,2],[2,3,3],[3,5]]

觀察到其中會輸出一個[2,2,3]和[2,5]的結果，這讓我非常困惑，因為我的代碼中明確了只有當curSum == target時才能進入存放結果的分支條件中，而此時這兩個數組的求和顯然應該是7而不是目標給出的8。這個問題讓我百思不得其解，檢查了很久都沒想通。（如果有讀者看到這里，也可以嘗試一下閱讀上面代碼找一下問題所在）

為了找出這個問題，我甚至在Visual Studio中逐行deBug，最終終于發現了問題所在。

原來問題在于其中的sort。當我在if分支中使用sort對當前數組進行排序的時候，即：

  if(curSum == target){
      sort(curVec.begin(), curVec.end()); // 此時對curVec進行排序，會導致curVec的順序改變，不再按照我存入時的順序排列
      vecSet.insert(curVec); 
      return;
  }

而在使用了sort將順序打亂變為和我存入時的順序不同后，再我的for循環部分代碼中：

      for(int i = 0; i < candidates.size(); i++){
          curVec.push_back(candidates[i]); // 存入下一狀態的值
          curSum += candidates[i]; // 更新下一狀態的和
          combHelper(candidates, vecSet, curVec, curSum, target); // 這一步的遞歸中，可能會因為sort而改變數組的順序
          curSum -= candidates[i];  // 此時回溯減去的值和上一次加入的值相等
          curVec.pop_back(); // 但此時pop出vec的值，和上面存入的值可能因為sort而導致不是同一個數
      }

終于找出了問題所在，為此我們總結經驗：

• 在使用回溯遞歸的過程中，不要對傳入的包含了上一步狀態的變量進行修改。（例如此時傳入的curVec其實包含了回溯退回的路徑這個信息，如果對其進行sort，會導致回退到錯誤的狀態）。

同時總結本題的思路，上面我們使用sort其實是為了去重而引入的，但是引入之后反而導致產生了錯誤。為此我們需要尋找其他的去重方法。思考昨天所做的回溯題目中，我們是通過設定startPoint來限定每一次for循環開始的值，從而規避了重復的情況，接下來我們嘗試使用同樣的方法來解決本題。

正確的回溯解法

上一節中展示了一種錯誤的去重方式，這里考慮給每次傳入遞歸函數中的參數新增一個int類型的start變量，用于表示每次搜索下一狀態時的起始搜索狀態，從而避免重復。這樣我們可以寫出代碼如下：

class Solution {
public:
    void combHelper(vector<int>& candidates, int target, int start){
        if(curSum == target){ // 終止條件
            result.push_back(curVec);
            return;
        }
        if(curSum > target) return; 

        for(int i = start; i < candidates.size(); i++){ 
            curVec.push_back(candidates[i]); // 存儲當前狀態
            curSum += candidates[i];
            combHelper(candidates, target, i); // 根據for循環中i的取值從不同的點開始遞歸
            curSum -= candidates[i];  // 回溯
            curVec.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        combHelper(candidates, target,0); 
        return result; 
    }
private:
    vector<vector<int>> result; // 在類中用全局變量來存儲結果數組，以及表示當前狀態的curVec和curSum
    vector<int> curVec;
    int curSum = 0;
};

上面的回溯可以看做是對一個多叉樹的深度優先搜索，先搜索了全部i=0時的結果，隨后隨著i增加，再去搜索其他分支（這里可以保證搜索分支序號i具有一個單調不減的性質）。同時每一次的start都是從i開始，表示了可以和上一個節點相同，而如果要與上一個節點不同，即每個節點不能重復的話，每次調用傳入的start就該變為i+1。

Leecode 40.組合總和II

題目描述

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

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

注意：解集不能包含重復的組合。

• 示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:

[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

• 示例 2:

輸入: candidates = [2,5,2,1,2], target = 5,
輸出:

[
[1,2,2],
[5]
]

解題思路

首先需要充分理解本題，特別是本題和上一題以及昨天所做的216. 組合總和 III的區別。區別主要就在于，本題給定的向量中的數是有重復的，同時其中每一個數只能使用一次。同時還需要注意，本題輸出的結果需要和此前做過的組合一樣，最終結果都是不重復的。在這里我們可以舉一個例子：

當輸入 candidates = [1, 1, 2], target = 3時
由于輸入的candidates中有重復元素，而在檢查到由第一個1組成的[1,2]后發現和為3進行存入，隨后又遇到第二個1組成[1,2]會再次進行存入，此時就相當于在結果中存放了兩個一模一樣的[1,2]。這會導致最終結果會產生重復值。

為了解決上面提到的重復問題，即為了避免在輸出的vec中同一個位置取到candidates中不同的數但卻是相等的值，我們可以將原本的vector先進行一次排序。這樣就可以使得所有相等的值都相鄰，隨后在此基礎上再繼續考慮去重。

在原本的candidates有序之后，如果要去重，當然還是可以考慮使用set容器（盡管在上一題中嘗試使用set得到了錯誤的結果）。為此我們可以寫出如下代碼：

class Solution {
public:
    set<vector<int>> result;  // 使用set來存放進行去重
    vector<int> curVec;
    int curSum = 0;

    void combHelper(vector<int>& candidates, int target, int start){
        if(curSum == target){ 
            result.insert(curVec);
            return;
        }
        if(curSum > target) return;

        for(int i = start; i < candidates.size() && curSum + candidates[i] <= target; i++){
            curVec.push_back(candidates[i]);
            curSum += candidates[i];
            combHelper(candidates, target, i+1);
            curSum -= candidates[i];
            curVec.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        combHelper(candidates, target, 0);
        vector<vector<int>> result1(result.begin(), result.end());
        return result1;
    }
};

上面代碼確實沒啥問題，測試算例也基本上都能跑過，但是在遇到測試算例：

輸入：

candidates = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
target = 30

會發生超時的情況，原因是當輸入全為 1 的數組且目標值較大（如 30）時，你的代碼會遍歷所有可能的組合（如 C(100,30) 種），并通過 set 去重。盡管最終結果唯一，但遍歷所有可能路徑的時間復雜度達到指數級，導致超時。

因此為了避免不必要重復帶來的時間復雜度，我們應該嘗試使用其他的方法來去重。特別是需要避免同一層循環中出現相同值的情況。為此我們可以寫出下面代碼：

class Solution {
public:
    vector<vector<int>> result;
    vector<int> curVec;
    int curSum = 0;

    void combHelper(vector<int>& candidates, int target, int start) {
        if (curSum == target) {
            result.push_back(curVec);
            return;
        }
        if (curSum > target) return;

        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;  // 跳過同層級重復元素，從而進行去重操作，使用continue跳過
            if (curSum + candidates[i] > target) break; // 剪枝，如果當前值求和已經大于目標和，則沒必要再試探后續的結果，直接break

            curVec.push_back(candidates[i]);
            curSum += candidates[i];
            combHelper(candidates, target, i+1);
            curSum -= candidates[i];
            curVec.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); 
        combHelper(candidates, target, 0);
        return result;
    }
};

此時的回溯代碼就可以正常通過測試了。

Leecode 131.分割回文串

題目描述

給你一個字符串 s，請你將 s 分割成一些 子串，使每個子串都是 回文串 。返回 s 所有可能的分割方案。

• 示例 1：

輸入：s = "aab"
輸出：[["a","a","b"],["aa","b"]]

• 示例 2：

輸入：s = "a"
輸出：[["a"]]

解題思路

這道題做起來感覺有點難度，首先一上手就不知道如何分割字符串，專門去查了一下字符串自帶的函數，本題中主要用到：

• substr(i,j)，表示將字符串中從序號i到j的左閉右閉區間組成一個新的字符串

再按照回溯的方法寫出下面代碼：

class Solution {
public:
    vector<vector<string>> result;
    vector<string> curVec;

    bool isPalindrome(string curStr){
        int n = curStr.size();
        for(int i = 0; i < n/2 ; i++){
            if(curStr[i] != curStr[n-1-i]) return false;
        }
        return true;
    }

    void partHelper(const string& s, int start){
        if(s.size() <= start){ // 如果start已經超出s中所有的數
            result.push_back(curVec); // 將當前向量存放
            return;
        }
        for(int i = start; i < s.size(); i++){ // 用[start,i]左閉右閉區間來表示當前字符串，遍歷i取到之后所有長度
            string newStr = s.substr(start, i - start + 1); // 建立當前字符串
            if(isPalindrome(newStr)){ // 如果當前字符串是回文串
                curVec.push_back(newStr); // 存入curVec中
                partHelper(s, i+1); // 遞歸
                curVec.pop_back(); // 回溯
            }
        }
    }

    vector<vector<string>> partition(string s) {
        partHelper(s, 0);
        return result;
    }
};

上面代碼中難點在于，使用start變量來表示字符串中的子串的起始位置，另外是每次遞歸回溯要先進行一個if判斷，判斷其是否為回文串。而對于之前幾題組合的回溯代碼中，并沒有其他的判斷而直接進行遞歸回溯。

今日總結

進一步學習了回溯算法，回溯中遞歸函數傳入的start變量非常常見，通常在組合中可以用于控制去重、字符串中用于表示子字符串的起始值。
此外在回溯的for循環中，可以通過加上if判斷語句來去重、剪枝（相應地在if內加上break或者continue），要根據具體的問題來討論分析，靈活應對。

今天刷到85題了，再接再厲！