Leetcode: 216 組合總和III

經(jīng)過了昨天組合的題目的學(xué)習(xí)，這道題比較簡單，套用之前的模板就可以

基本思路

• 終止條件，遇到向量的個數(shù)一樣，并且sum等于n的時候終止。
• 輸入變量，n,k，還有起始的idx和基于當(dāng)前元素之和的sum
• 邏輯就是，按照循環(huán)遞歸下去，注意要對sum值進行回溯。

時間復(fù)雜度O(n * 2^n)

空間復(fù)雜度O(N)

class Solution {
private:
    vector<vector<int>> result;
    vector<int> vec;
    void traceback(int k, int n, int idx, int sum){
        if(vec.size() == k && sum == n){
            result.push_back(vec);
            return;
        }
        for(int i = idx; i <= 9; i++){
            vec.push_back(i);
            sum += i;//計算當(dāng)前元素之和
            traceback(k, n, i+1, sum);//進行遞歸
            sum -= i;//注意sum值的回溯
            vec.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        traceback(k, n, 1, 0);
        return result;
    }
};

減枝優(yōu)化

1、每個數(shù)值的取值范圍為1-9，與上題一樣的剪枝操作。2、當(dāng)所有元素之和已經(jīng)大于n的時候后續(xù)就不需要進行遞歸了。

for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
    sum += i; // 處理
    path.push_back(i); // 處理
    if (sum > targetSum) { // 剪枝操作
        sum -= i; // 剪枝之前先把回溯做了
        path.pop_back(); // 剪枝之前先把回溯做了
        return;
    }
    backtracking(targetSum, k, sum, i + 1); // 注意i+1調(diào)整startIndex
    sum -= i; // 回溯
    path.pop_back(); // 回溯
}

Leetcode: 17 電話號碼的字母組合

字母和數(shù)字的映射

需要先定義一個二維數(shù)組來存放映射關(guān)系。

const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
};

基本思路

• 輸入：要求的digit和定義一個idx來記錄目前遍歷到哪個數(shù)字了。
• 終止條件，當(dāng)遍歷的數(shù)字和digit長度一樣的時候。
• 遍歷邏輯：首先要取index指向的數(shù)字，并找到對應(yīng)的字符集（手機鍵盤的字符集）。

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;
    string str;
    void traceback(string digits, int idx){
        if(idx == digits.size()){
            result.push_back(str);
            return;
        }
        int digit = digits[idx] - '0';        // 將idx指向的數(shù)字轉(zhuǎn)為int
        string letters = letterMap[digit];      // 取數(shù)字對應(yīng)的字符集
        for (int i = 0; i < letters.size(); i++) {
            str.push_back(letters[i]);            // 處理
            traceback(digits, idx + 1);    // 遞歸，注意index+1，一下層要處理下一個數(shù)字了
            str.pop_back();                       // 回溯
        }

    }

    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return result;
        }
        traceback(digits, 0);
        return result;
    }
};

本題的難點主要在于1、字母表和數(shù)字的映射建立和相互轉(zhuǎn)換 2、遞歸邏輯的梳理文章來源地址http://www.zghlxwxcb.cn/news/detail-808979.html

到了這里，關(guān)于DAY25：回溯算法組合題216、17的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！