天天看點
傳回

代碼随想錄1刷—回溯篇（一）

代碼随想錄1刷—回溯篇（一）

      • 回溯理論基礎
        • 回溯法可以解決的問題
        • 回溯算法模闆架構
      • [77. 組合](https://leetcode.cn/problems/combinations/)
        • 剪枝處理
      • [216. 組合總和 III](https://leetcode.cn/problems/combination-sum-iii/)
        • 剪枝處理
      • [17. 電話号碼的字母組合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)
        • 數字和字母的映射
        • 回溯藏在遞歸參數中的寫法
      • [39. 組合總和](https://leetcode.cn/problems/combination-sum/)
        • 剪枝處理
      • [40. 組合總和 II](https://leetcode.cn/problems/combination-sum-ii/)
        • 題外話：continue和break的差別
      • [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)
      • [93. 複原 IP 位址](https://leetcode.cn/problems/restore-ip-addresses/)
      • [78. 子集](https://leetcode.cn/problems/subsets/)

回溯理論基礎

回溯是遞歸的副産品，隻要有遞歸就會有回溯。

回溯的本質是窮舉，窮舉所有可能，然後選出我們想要的答案，如果想讓回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是窮舉的本質。雖然回溯法是個非常低效的辦法，但一些問題隻能用回溯來解決。還沒有更高效的解法。

回溯法可以解決的問題

  • 組合問題：N個數裡面按一定規則找出k個數的集合
  • 切割問題：一個字元串按一定規則有幾種切割方式
  • 子集問題：一個N個數的集合裡有多少符合條件的子集
  • 排列問題：N個數按一定規則全排列，有幾種排列方式
  • 棋盤問題：N皇後，解數獨等等

回溯算法模闆架構

回溯法一般是在集合中遞歸搜尋，集合的大小構成了樹的寬度，遞歸的深度構成的樹的深度。

代碼随想錄1刷—回溯篇（一）
void backtracking(參數) {
    if (終止條件) {
        存放結果;
        return;
    }
    for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
        處理節點;
        backtracking(路徑，選擇清單); // 遞歸
        回溯，撤銷處理結果
    }
}

77. 組合

代碼随想錄1刷—回溯篇（一）

每次從集合中選取元素，可選擇的範圍随着選擇的進行而收縮，調整可選擇的範圍。（是以需要一個參數，為int型變量startIndex，這個參數用來記錄本層遞歸的中，集合從哪裡開始周遊）

n相當于樹的寬度，k相當于樹的深度。圖中每次搜尋到了葉子節點，我們就找到了一個結果。

class Solution {
private:
    vector<vector<int>> result; 
    vector<int> path;
    void backtracking(int n,int k,int startIndex){
        if(path.size() == k){   //周遊到葉子節點
            result.push_back(path);
            return;
        }
        for(int i  = startIndex;i <= n;i++){    //橫向周遊
            path.push_back(i);  //處理結點
            backtracking(n,k,i+1);  //遞歸
            path.pop_back();    //回溯，撤銷處理的結點
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n,k,1);
        return result;
    }
};

剪枝處理

可以剪枝的地方就在遞歸中每一層的for循環所選擇的起始位置。如果for循環選擇的起始位置之後的元素個數 已經不足 我們需要的元素個數了，那麼就沒有必要搜尋了。比如n=4，k=4的情況下，隻要選1，2，3，4就完成了，選2，3，4根本無法滿足。

優化過程如下：

  1. 已經選擇的元素個數：path.size();
  2. 還需要的元素個數為: k - path.size();
  3. 在集合n中至多要從該起始位置 : n - (k - path.size()) + 1，開始周遊

為什麼有個+1呢，因為包括起始位置是一個左閉的集合。舉個例子，n = 4，k = 3， 目前已經選取的元素為0（path.size為0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。從2開始搜尋都是合理的，可以是組合[2, 3, 4]。

//	将for循環進行優化剪枝
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i為本次搜尋的起始位置
           
class Solution {
private:
    vector<vector<int>> result; 
    vector<int> path;
    void backtracking(int n,int k,int startIndex){
        if(path.size() == k){   //周遊到葉子節點
            result.push_back(path);
            return;
        }
        for(int i = startIndex;i <= n - (k-path.size()) + 1;i++){
            path.push_back(i);              //處理結點
            backtracking(n,k, i + 1);       //遞歸
            path.pop_back();                //回溯，撤銷處理的結點
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n,k,1);
        return result;
    }
};

216. 組合總和 III

處理過程 和 回溯過程是一一對應的，處理有加，回溯就要有減！

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int k,int n,int startIndex,int sum){
        if(path.size() == k){
            if(sum == n)
                result.push_back(path);
            else
                return;
        }
        for(int i = startIndex;i <= 9;i++){
            sum += i;
            path.push_back(i);
            backtracking(k,n,i + 1,sum);    //遞歸
            sum -= i;
            path.pop_back();   //回溯
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtracking(k,n,1,0);
        return result;
    }
};

剪枝處理

已選元素總和如果已經大于n了，那麼往後周遊就沒有意義了，直接剪掉。

if(sum > n){	//剪枝優化
	return;
}
           
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int k,int n,int startIndex,int sum){
        if(sum > n){
	        return;
        }
        if(path.size() == k){
            if(sum == n)
                result.push_back(path);
            else
                return;
        }
        for(int i = startIndex;i <= 9;i++){
            sum += i;
            path.push_back(i);
            backtracking(k,n,i + 1,sum);    //遞歸
            sum -= i;
            path.pop_back();   //回溯
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtracking(k,n,1,0);
        return result;
    }
};

17. 電話号碼的字母組合

數字和字母的映射

可以使用map或者定義一個二維數組。

const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
};
代碼随想錄1刷—回溯篇（一）
class Solution {
private:
    const string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };

    vector<string>  result;
    string s;
    void backtracking(const string& digits , int index){
        		//const string&為常引用
        //引用作為函數參數進行傳遞時，實質上傳遞的是實參本身，即傳遞進來的不是實參的一個拷貝，是以對形參的修改其實是對實參的修改，是以在用引用進行參數傳遞時，不僅節約時間，而且可以節約空間。
        //index 為記錄周遊第幾個數字了，就是用于周遊digits的
        if(index == digits.size()){    //終止條件
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';    //  将digits[index]指向的字元轉為int
        string letters = letterMap[digit];  //  取得數字對應的字元集
        for(int i = 0;i < letters.size();i++){
            //注意：這裡for循環，可不像是在[77. 組合]和[216. 組合總和 III]中從startIndex開始周遊的。
            //因為本題每一個數字代表的是不同集合，也就是求不同集合之間的組合，而76和216的題都是是求同一個集合中的組合
            s.push_back(letters[i]);
            backtracking(digits,index + 1);
            s.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if(digits.size() == 0){
            return result;
        }
        backtracking(digits,0);
        return result;
    }
};

回溯藏在遞歸參數中的寫法

在遞歸參數和遞歸函數使用兩句話中有變化，其他部分都一樣，這種寫法不直覺，不建議這樣寫，但要了解。

class Solution {
private:
        const string letterMap[10] = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
        };
public:
    vector<string> result;
    void getCombinations(const string& digits, int index, const string& s) { 
        												// 注意參數的不同
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); i++) {
            getCombinations(digits, index + 1, s + letters[i]);  
            										// 注意這裡的不同
        }
    }
    vector<string> letterCombinations(string digits) {
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        getCombinations(digits, 0, "");
        return result;

    }
};

39. 組合總和

本題和77題和216題的差別是：本題沒有數量要求，可以無限重複，但是有總和的限制。

在77和216題中知道要遞歸K層，因為要取k個元素的組合。但本題不是，注意圖中葉子節點的傳回條件，因為本題沒有組合數量要求，是總和的限制，是以遞歸沒有層數的限制，隻要選取的元素總和超過target，就傳回！

代碼随想錄1刷—回溯篇（一）
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates,int target,int sum,int startIndex){
        if(sum > target){
            return;
        }
        if(sum == target){
            result.push_back(path);
            return;
        }
        for(int i = startIndex;i < candidates.size();i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,i);  //不用i+1了，因為可以重複讀取數值
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates,target,0,0);
        return result;
    }
};

剪枝處理

對于sum已經大于target的情況，其實是依然進入了下一層遞歸，隻是下一層遞歸結束判斷的時候，會判斷sum > target的話就傳回。其實如果已經知道下一層的sum會大于target，就沒有必要進入下一層遞歸了。是以可以在for循環的搜尋範圍上做做文章了。

對總集合排序之後，如果下一層的sum（就是本層的 sum + candidates[i]）已經大于target，就可以結束本輪for循環的周遊。注意：是排序之後！！

代碼随想錄1刷—回溯篇（一）

for循環剪枝代碼如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates,int target,int sum,int startIndex){
        if(sum == target){
            result.push_back(path);
            return;
        }
        for(int i = startIndex;i < candidates.size() && sum + candidates[i] <= target;i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,i);  //不用i+1了，因為可以重複讀取數值
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(),candidates.end());      //記得排序
        backtracking(candidates,target,0,0);
        return result;
    }
};

在求和問題中，排序之後加剪枝是常見的套路！

40. 組合總和 II

  1. 本題candidates 中的每個元素在每個組合中隻能使用一次。
  2. 本題數組candidates的元素是有重複的
  3. 解集不能包含重複的組合。

難點就在于2和3，在搜尋的過程中需要去掉重複組合，元素在同一個組合内是可以重複的，怎麼重複都沒事，但兩個組合不能相同。是以要去重的是同一樹層上的“使用過”，而同一樹枝上的都是一個組合裡的元素，不用去重。另一方面需要注意的是：樹層去重的話，需要對數組排序！

代碼随想錄1刷—回溯篇（一）

bool型數組used：是用來記錄同一樹枝上的元素是否使用過。這個集合去重的重任就是used來完成的。

代碼随想錄1刷—回溯篇（一）

可以看出在candidates[i] == candidates[i - 1]相同的情況下：

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

如果

candidates[i] == candidates[i - 1]

并且

used[i - 1] == false

，說明前一個樹枝使用了candidates[i - 1]，也就是說同一樹層使用過candidates[i - 1]，此時for循環裡就應該做continue的操作。

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++){
            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); //i是元素可以重複，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();
        sort(candidates.begin(),candidates.end());  //一定要記得排序！
        backtracking(candidates,target,0,0,used);
        return result;
    }
};

題外話：continue和break的差別

continue語句的作用是跳過本次循環體中餘下尚未執行的語句，立即進行下一次的循環條件判定，可以了解為僅結束本次循環。而break會直接結束該循環。

131. 分割回文串

本題涉及到兩個關鍵問題：

  1. 切割問題
  2. 切割後判斷回文

其實切割問題類似組合問題。例如對于字元串abcdef：

  • 組合問題：選取一個a之後，在bcdef中再去選取第二個，選取b之後在cdef中在選組第三個…。
  • 切割問題：切割一個a之後，在bcdef中再去切割第二段，切割b之後在cdef中在切割第三段…。
代碼随想錄1刷—回溯篇（一）

遞歸用來縱向周遊，for循環用來橫向周遊，切割線（就是圖中的紅線）切割到字元串的結尾位置，說明找到了一個切割方法。

class Solution {
private:
    bool isPalindrome(const string& s,int start,int end){
        for(int i = start,j = end;i<j;i++,j--){
            if(s[i]!=s[j]){
                return false;
            }
        }
        return true;
    }
    vector<vector<string>>  result;
    vector<string>  path;
    void backtracking(const string& s,int startIndex){
        if(startIndex >= s.size()){
            result.push_back(path);
            return;
        }
        for(int i = startIndex;i < s.size();i++){
            if(isPalindrome(s,startIndex,i)){   //是回文子串
                //擷取[startIndex,i]在s中的子串
                string str = s.substr(startIndex,i - startIndex + 1);  
                             //substr 複制子字元串（從指定位置開始，指定的長度）
                path.push_back(str);
            }else{
                continue;
            }
            backtracking(s,i + 1);  //切割過的位置不可以重複切割，是以i+1
            path.pop_back();
        }
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        backtracking(s,0);
        return result;
    }
};

93. 複原 IP 位址

代碼随想錄1刷—回溯篇（一）
class Solution {
private:
    vector<string>  result;
    void backtracking(string& s, int startIndex,int pointNum){
        if(pointNum == 3){   // 三個點分成四段
            //判斷第四段是否合法
            if(isValid(s,startIndex,s.size()-1)){
                result.push_back(s);
            }
            return;
        }
        for(int i = startIndex;i < s.size();i++){
            if(isValid(s,startIndex,i)){
                s.insert(s.begin() + i + 1,'.');
                pointNum++;
                backtracking(s,i + 2,pointNum);   //因為加了個點 是以從i+1變成i+2了
                pointNum--;
                s.erase(s.begin() + i + 1);
            }else break;    //不合法直接結束本層循環
        }
    }
    bool isValid(const string& s,int start,int end){
        if(start > end) return false;
        if(s[start] == '0' && start != end){
            return false;
        }
        int num = 0;
        for(int i = start;i <= end;i++){
            if(s[i] > '9' || s[i] < '0'){
                return false;
            }
            num = num*10 + (s[i]-'0');
            if(num > 255){
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if(s.size() < 4 || s.size() > 12) 
            return result;
        backtracking(s,0,0);
        return result; 
    }
};

78. 子集

代碼随想錄1刷—回溯篇（一）

剩餘集合為空的時候，就是葉子節點。那麼什麼時候剩餘集合為空呢？實際上，當startIndex已經大于數組的長度了，就終止了，因為沒有元素可取了。

需要注意的是，for (int i = startIndex; i < nums.size(); i++) 中如果startIndex >= nums.size()，for循環也就結束了，是以這個終止條件可加可不加，不影響最終結果。

求取子集問題，不需要任何剪枝！因為子集就是要周遊整棵樹。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex){
        result.push_back(path); 
        	//注意要在終止條件之前收集子集，否則會漏掉終止時的那個集合
        if(startIndex >= nums.size()){  
            //由于後面for循環的條件，此終止條件判斷可加可不加，為了邏輯的完整性還是加上
            return;
        }
        for(int i = startIndex;i < nums.size();i++){
            path.push_back(nums[i]);
            backtracking(nums,i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums,0);
        return result;
    }
};
筆試混子準備 算法 leetcode 資料結構 剪枝
上一篇: 代碼随想錄1刷—回溯篇（二）
下一篇: CSS面試題-如何實作左邊定寬，右邊自适應

繼續閱讀