回溯理論

什麼是回溯

回溯，顧名思義，返回溯源，記錄當前節點後返回前一節點繼續的過程。本質上是一種羅列所有情況的窮舉搜索。

遞歸

遞歸，函數間接或者直接調用自身，回到最初最簡單的情況。目前的情況歸根結底就是一棵樹的情況。

回溯與遞歸

為什麼説回溯常常伴隨遞歸？遞歸是把一棵大二叉樹返回到一個最基本的三個節點的樹，在每一次樹變小的過程中，都有一個數的子樹返回根節點的過程。

n個數中k個數的組合

問題

1.返回值問題
2.私有成員變量

代碼

class Solution {
private:
    vector<int> vec;
    vector<vector<int>> res;

public:
    void backTrack(int n, int k, int startIndex) {
        if (vec.size() == k) {
            res.push_back(vec);
            return;
        }
        for (int i = startIndex; i <= n-(k-vec.size()+1); i++) {
            vec.push_back(i);
            backTrack(n, k, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backTrack(n, k, 1);
        return res;
    }
};

總結

組合相當於把K層循環的過程用遞歸來實現。樹的寬度要遍歷的數組中的每一個元素，是循環的第一層。

k個不相同數相加為n的組合

思路

1.遞歸函數的返回值和參數
返回值是void類型，參數是傳入的n與k。以及用sum記錄當前的和。
2.終止條件
相加為n且是k個數；
3.單層遞歸的邏輯
一層循環下面，每次sum+i，壓入；
回溯過程和處理過程一一對應。

代碼

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtrack(int n, int k,int sum, int startIndex) {
        if (sum == n&&path.size()==k) {
            res.push_back(path);
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i;
            path.push_back(i);
            backtrack(n, k, sum, i + 1);
            sum -= i;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        int sum=0;
        backtrack(n,k,sum,1);
        return res;
    }
};

電話鍵有限數字對應的字母組合

思路

1.建立數字與字母的映射關係；const string lettermap[10]={,,}
2.樹的寬度與遞歸的深度；
3.回溯過程
結果用一個字符串string s和一個字符串數組vector res保存；
<1>確定返回值（void）和參數（digits,int index）;
<2>確定終止條件：string的長度和digit的長度相等；digits.size()==index
<3>單層循環邏輯
壓入--遍歷--彈出

代碼

class Solution {
public:
    vector<string> res;
    string path;
    const string lettermap[10] = {",",   ",",   "abc",  "def", "ghi",
                                  "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void backTrack(string&digits, int index) {
        if (index == digits.size()) {
            res.push_back(path);
            return;
        }
        // 建立數字--字母映射
        int digit = digits[index] - '0'; // 把字符類型轉化為int;
        string letters = lettermap[digit]; // 建立數字和字母的對應關係;
        for (int i = 0; i <letters.size() ; i++) {
            path.push_back(letters[i]);
            backTrack(digits, index + 1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        backTrack(digits, 0);
        return res;
    }
};