回溯演算法

1、回溯演算法的概念

xxxx回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法，回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試，
xxxx上述文字有些抽象，如果將其具化來說，回溯法思路的具體描述是：把問題的解空間轉化成了圖或者樹的結構表示，然后使用深度優先搜索策略進行遍歷，遍歷的程序中記錄和尋找所有可行解或者最優解，

2、回溯演算法的一般解題思路

1、定義一個解空間，它包含問題的解，

2、利用適于搜索的方法組織解空間，

3、利用深度優先法搜索解空間，

4、利用限界函式避免移動到不可能產生解的子空間，

注：問題的解空間通常是在搜索問題的解的程序中動態產生的，這是回溯演算法的一個重要特性

3、解決問題的方法

xxxx對于常見的問題，既然我們將其解空間轉化為了多叉樹的深度優先遍歷（DFS）/后序遍歷，那么我們最常用的方法就是遞回！！

xxxx總結：我們在不斷“嘗試”之后就可以得到最終的結果，嘗試的程序就是不斷的列舉式的對每種情況進行檢驗，找出符合題目要求的結果，

例題一：二叉樹中和為某一值的路徑

（1）題目描述

（2）題目分析

xxxx這道題其實比較簡單，因為它直接具化成或者本身就是二叉樹，所以，我們直接對這個二叉樹進行操作即可，并不需要化抽象為具象，把一個事物轉化為二叉樹，而對于這道題，我們就需要從根節點出發，按照【根，左子樹，右子樹】這種前序的遍歷序列，而前序遍歷，我們在處理根的時候，處理的內容就是到這個節點時，路徑值之和，只有當節點是葉子節點，并且路徑值之和等于目標值即是答案之一，

（3）代碼實作

class Solution {
	//遞回子函式
	//引數ret，因為ret要實時變化，所以我們要傳參考
	//引數ans，因為，每次到達一個結點，都要將值push進ans，但是到葉子結點才能判斷是否正確，當我們回溯時，前一個的路徑不是下一個路徑，遞回回去時，值不應該改變，因此要傳值
	//引數sum，到達某一結點后路徑值和，也同ans一樣道理，不能實時改變
	//目標值固定，是否使用參考都可
    void pathSumHelper(TreeNode* root, vector<vector<int>>& ret, vector<int> ans, int sum, int& target)
    {
    	//如果訪問到空結點，直接回傳即可
        if(root == nullptr)
            return;
        //不是空結點，處理該結點（前序遍歷）
        sum += root->val;//sum+該結點值
        ans.push_back(root->val);//把該結點作為路徑push到當前路徑ans中
		//開始判斷，如果是葉子結點，并且路徑值之和==目標值，就是正確結果，push進ret
        if(root->left==nullptr &&root->right==nullptr && sum==target)
        {
            ret.push_back(ans);
            return;
        }
        //分別處理左右子樹
        pathSumHelper(root->left,ret,ans,sum,target);
        pathSumHelper(root->right,ret,ans,sum,target);
    }

public:
	//“主函式”
    vector<vector<int>> pathSum(TreeNode* root, int target) {
    	//用于保存最后結果的vector
        vector<vector<int>> ret;
        //保存每一個路徑，會隨著遞回進行
        vector<int> ans;
        //遞回子函式
        //引數：排查的結點，最侄訓傳的vector，每一個路徑，路徑值之和，目標路徑和
        pathSumHelper(root,ret,ans,0,target);
        return ret;
    }
};

例題二：電話號碼的字母組合

（1）題目描述

（2）題目分析

xxxx這道題，乍一看可能沒有上一道題那么直接就是看出來是樹狀但是其實想到他是回溯演算法也不難，
xxxx這道題就是想得到所有情況，跟一個一個嘗試沒有區別，只不過它無需判斷是否符合條件，只需要將嘗試的結果全部接收就好
xxxx對于所有情況，我覺得大家初中時候就學到過“樹狀圖”----用于處理所有可能發生的情況，將所有的情況列出的一種樹狀結構，這道題就是這種，為了將所有情況列出，就可以采取樹狀圖，下面通過舉一個例子，我給大家把樹狀圖實作一下，

xxxx通過這個樹狀圖我們就可以清楚的明白，這就是一個樹狀結構，有幾個數字，就相當于，這個要遞回多少次，按照前序遍歷的方式，我們就可以將所有的結果得到，

（3）代碼實作

//這是一個小細節，我們定義一個全域的vector<string>，對應數字我們就可以通過這個vector找到對應的所有字母
vector<string> character={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
class Solution {
public:
	//遞回子函式
    void _letterCombinations(const string& digits, vector<string>& ret, int k,string str)
    {
    	//如果k等于了digits的size，說明，所有數字都取完了，一條路徑結束，第一次遞回結束，是遞回的出口，
        if(k == digits.size())
        {
            ret.push_back(str);
            return;
        }
        //取到數字
        int num = digits[k]-'0';
        //for回圈，遍歷對應數字的所有字母，每個字母分別對應自己的遞回，形成樹狀結構
        for(int i=0;i<character[num].size();i++)
        {
        	//取到該字母
           char ch = character[num][i];
//k+1,說明要進行下一個數字，str+ch，將本數字對應的字母添加到str中，保存路徑
//繼續遞回           _letterCombinations(digits,ret,k+1,str+ch);
        }
    }
    //主函式
    vector<string> letterCombinations(string digits) {
    	//也是定義一個用于存盤每一個字串的string
        string  str;
        //存盤所有的結果
        vector<string> ret;
        //如果digits是空的，就直接回傳
        if(digits.empty())
            return ret;
        //引數：digits存盤數字的字串
        //ret存盤最終的結果
        //0，digits的其實位置為0
        //str，存每一條路徑，最后將每一條完整的路徑push進ret
        _letterCombinations(digits,ret,0,str);
        return ret;
    }
};