Leecode 77. 組合

題目描述

給定兩個整數(shù) n 和 k，返回范圍 [1, n] 中所有可能的 k個數(shù)的組合。

你可以按 任何順序 返回答案。

• 示例 1：

輸入：n = 4, k = 2
輸出：

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

• 示例 2：

輸入：n = 1, k = 1
輸出：[[1]]

解題思路與代碼展示

本題要求給出所有滿足組合情況，使用窮舉法逐個嘗試，如果滿足則存入結(jié)果數(shù)組中。但直接寫的過程中會遇到兩個比較難處理的點：

• 如果每次要求的數(shù)的個數(shù)固定，比如滿足條件的3個數(shù)存入數(shù)組中，那么就只需使用3層for循環(huán)即可，即需要幾個數(shù)就使用幾層for循環(huán)。但題目所給的數(shù)的個數(shù)并不固定，故此時需要使用回溯（遞歸）的方式來進行處理。
• 此外，還需要確保輸出的數(shù)組沒有重復(fù)，即每次搜索過的數(shù)不會進行二次搜索。為了避免重復(fù)查找，可以設(shè)置一個查找的初始值，每次遞歸的時候傳入該值并從這個值開始往后遞歸搜索。

綜合上面思路，可以寫出代碼如下：

class Solution {
public:
    vector<vector<int>> result; // 使用兩個全局變量來存儲結(jié)果值和過程中每一次搜索的結(jié)果
    vector<int> curVec;

    void combineHelper(int n, int k, int startindex){ // 遞歸函數(shù)
        if(curVec.size() == k) { // 如果vector當前大小為k，則說明已經(jīng)符合條件，直接push存放入結(jié)果中
            result.push_back(curVec); 
            return;
        }
        for(int i = startindex; i <= n-(k-curVec.size()) + 1; i++){ // 使用for循環(huán)遍歷，相當于每次遞歸調(diào)用都有一層for循環(huán)；并從startindex開始搜索。其中終止條件中i的上界是剪枝后的結(jié)果，排除了一些不可能的情況，可以加速搜索。
            curVec.push_back(i);  // 將當前數(shù)存入當前vector中
            combineHelper(n, k, i+1); // 遞歸調(diào)用
            curVec.pop_back(); // 回溯退回
        }
    }

    vector<vector<int>> combine(int n, int k) {
        combineHelper(n,k,1); // 遞歸調(diào)用輔助函數(shù)
        return result; // 返回結(jié)果
    }
};

Leecode 216. 組合總和 III

題目描述

找出所有相加之和為 n 的 k 個數(shù)的組合，且滿足下列條件：

• 只使用數(shù)字1到9
• 每個數(shù)字 最多使用一次

返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

• 示例 1:

輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。

• 示例 2:

輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
解釋:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
沒有其他符合的組合了。

• 示例 3:

輸入: k = 4, n = 1
輸出: []
解釋: 不存在有效的組合。
在[1,9]范圍內(nèi)使用4個不同的數(shù)字，我們可以得到的最小和是 1 + 2 + 3 + 4 = 10，因為10 > 1，沒有有效的組合。

解題思路與代碼展示

本題和上面一題比較類似，使用相似的方法即可，區(qū)別在于遞歸終止條件中要多考慮如果求和值大于目標的情況，此時不滿足條件，直接退回即可。

class Solution {
public:
    vector<int> curVec; // 使用vector和curSum來記錄當前狀態(tài)，用于判斷是否滿足條件
    int curSum;
    vector<vector<int>> result; // result用于存放最終結(jié)果

    void combHelper(int k, int n, int startNum){
        if(curSum == n && curVec.size() == k){ // 如果數(shù)求和與數(shù)的個數(shù)都恰好滿足條件，則說明此時已經(jīng)滿足
            result.push_back(curVec); // 將滿足條件的vector存入結(jié)果中
        }
        else if(curSum > n) return; // 如果求和大于目標值，則一定不滿足，此時直接返回即可
        
        for(int i = startNum; i < 10 ; i++){ // 每一位數(shù)都從startNum開始遞歸求解
            curSum += i; // 更新當前總和，更新存儲的vec向量
            curVec.push_back(i);
            combHelper(k,n,i+1); // 遞歸搜索下一個數(shù)
            curSum -= i; // 回溯，此時要返回上一次的狀態(tài)，故需要同時恢復(fù)curSum和curVec
            curVec.pop_back(); 
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        combHelper(k, n, 1);
        return result;
    }
};

上面代碼關(guān)鍵在于遞歸返回進行回溯時，需要恢復(fù)所有遞歸過程中被修改的變量，在本題中需要同時回復(fù)curSum和curVec。

Leecode 17. 電話號碼的字母組合

題目描述

給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

• 示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

• 示例 2：

輸入：digits = ""
輸出：[]

• 示例 3：

輸入：digits = "2"
輸出：["a","b","c"]

解題思路與代碼展示

本題思路上不算難，在確定了使用回溯的方法后，只需要根據(jù)每次數(shù)字的不同從相應(yīng)可能得字母字符中依次選取進行回溯遞歸即可。但困難的點在于，總共有字母的按鍵包括2-9總共8個鍵，如果每一個鍵用一個if，同時內(nèi)部使用一個for循環(huán)進行回溯，會導(dǎo)致寫很多沒必要的重復(fù)代碼。為了避免這種情況需要使用一些方法來進行處理。我首先想到的第一種方法是合并前邊2-6個數(shù)字，因為前5個數(shù)每個數(shù)都剛好對應(yīng)3個字母，因此可以使用乘除法和取余運算來進行計算當前字母對應(yīng)哪些字母。但需要注意的是，這個計算過程中需要非常小心int類型與char類型之間的轉(zhuǎn)換，1的ASCII碼并不等于1，中間需要加減一個'0'才能進行轉(zhuǎn)換。

使用這種方法可以寫出代碼如下：

class Solution {
public:
    vector<string> result; // 同樣是使用全局變量來存儲結(jié)果和當前狀態(tài)的字符串
    string curStr;

    void combinationHelper(string digits, int curIndex){
        if(curIndex == digits.size()) { // 如果所有數(shù)字已經(jīng)遍歷結(jié)束，則將當前字符串存入結(jié)果中，并返回
            result.push_back(curStr);
            return;
        }
        if(digits[curIndex] < '7'){ // 對于前2-6的數(shù)，每個數(shù)都對應(yīng)三個字母，故可以放在一起處理
            for(int i = 0; i < 3; i++){ // for循環(huán)遍歷每個數(shù)對應(yīng)的三個字母
                curStr += ('a' + (digits[curIndex]-'0'-2)*3 ) + i%3; // 存入一個字母，此時要注意字符與int之間轉(zhuǎn)換需要減去一個值
                combinationHelper(digits, curIndex+1); // 遞歸調(diào)用存入下一個數(shù)字對應(yīng)的字母
                curStr.pop_back(); // 回溯
            }
        }
        else if(digits[curIndex] == '7' ){ // 處理完前2-6之后，采用同樣的方式處理7,8,9，區(qū)別在于7和9對應(yīng)4個字母，其余都一樣
            for(int i = 0 ; i < 4; i++){
                curStr += 'p' + i;
                combinationHelper(digits, curIndex+1);
                curStr.pop_back();
            }
        }
        else if(digits[curIndex] == '8'){
            for(int i = 0; i < 3; i++){
                curStr += 't' + i;
                combinationHelper(digits, curIndex+1);
                curStr.pop_back();
            }
        }
        else if(digits[curIndex] == '9'){
            for(int i = 0 ; i < 4; i++){
                curStr += 'w' + i;
                combinationHelper(digits, curIndex+1);
                curStr.pop_back();
            }
        }
    }

    vector<string> letterCombinations(string digits) {
        if(!digits.size()) return result;  // 如果輸入的字符串為空，則直接返回
        combinationHelper(digits, 0); // 使用回溯遞歸調(diào)用，將所有可能結(jié)果都存入result
        return result; // 返回result結(jié)果
    }
};

可以看到，上面代碼雖然確實在合并了一些情況的同時也能夠處理本題中的所有情況，但是對于數(shù)字取到7-9時，還是有大量重復(fù)代碼。為了簡化這部分內(nèi)容，考慮使用一個string類型的數(shù)組來存放每個數(shù)字對應(yīng)的字母。即：

string numLetterMap[10]{
     "",
     "",
     "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"
};

這樣每次使用將按鍵數(shù)字轉(zhuǎn)換為字母字符的時候，直接去數(shù)組中查找即可，這樣我們可以修改得到下面的代碼：

class Solution {
public:
    string numLetterMap[10]{ // 存放每個按鍵對應(yīng)的字母字符
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"
    };

    void combHelper(vector<string>& result, string digits, string curStr){
        if(curStr.size() == digits.size()){ // 如果已經(jīng)長度相等，說明已經(jīng)完成，此時需要存入結(jié)果中
            result.push_back(curStr);
            return;
        }
        int num = digits[curStr.size()] - '0'; // 首先將char類型的數(shù)字轉(zhuǎn)換為int類型
        for(int i = 0; i < numLetterMap[num].size(); i++){ // for循環(huán)下遍歷所有取值，注意此時循環(huán)次數(shù)取決于字符串數(shù)組中對應(yīng)位置的長度
            curStr += numLetterMap[num][i]; // 當前字符串上加一個字母
            combHelper(result, digits, curStr); // 遞歸
            curStr.pop_back(); // 回溯
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if(!digits.size()) return result;
        string curStr = "";
        combHelper(result, digits ,curStr);
        return result;
    }
};

通過上面代碼可以學(xué)到，之后再遇到討論情況比較多的時候，為了避免使用多個if或是switch等造成討論情況過多，可以考慮使用一些數(shù)據(jù)類型來存儲一部分信息，從而簡便討論。

今日總結(jié)

今天學(xué)習(xí)到了回溯算法，了解到回溯和遞歸的密不可分。回溯過程中會有一個或多個變量用于存放“當前狀態(tài)”，每一次使當前狀態(tài)變?yōu)橄乱粻顟B(tài)之后調(diào)用遞歸函數(shù)進行處理，遞歸結(jié)束之后還需要將當前進行恢復(fù)。同時回溯可以考慮使用一個全局變量來存放結(jié)果和當前狀態(tài)，或者是用引用傳遞的方式來確保可以進行修改。

此外，當遇到需要討論的情況比較多的時候，考慮能否使用一個數(shù)組來存儲不同情況下的一些取值，從而減少if討論分支，減少代碼量。

力扣當前刷到82題了，繼續(xù)堅持