前言

回溯算法中遞歸的邏輯不重要，只要掌握回溯的模板以及將問題轉(zhuǎn)化為樹形圖，整個問題就很好解決了，比二叉樹簡單。

?Leetcode 77 組合

題目鏈接：77. 組合 - 力扣（LeetCode）

代碼隨想錄題解：代碼隨想錄 (programmercarl.com)

思路：套回溯的模板，終止條件是path==k。然后將題目描述的組合邏輯想象成樹形結(jié)構(gòu)

代碼：

class Solution {
public:vector<int> path;vector<vector<int>>res;void backtracking(int n,int k, int index){if(path.size()==k)//終止條件{res.push_back(path);return;}for(int i=index;i<=n;i++)樹形結(jié)構(gòu)邏輯{path.push_back(i);backtracking(n, k, i+1);path.pop_back();回溯}return;}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return res;}
};

Leetcode 216 組合總和Ⅲ

題目鏈接：216. 組合總和 III - 力扣（LeetCode）

代碼隨想錄題解：代碼隨想錄 (programmercarl.com)

思路：這個題和上一道題唯一的區(qū)別就是終止條件加了一個和等于目標(biāo)值，樹形結(jié)構(gòu)基本沒變

代碼：

class Solution {
public:vector<int> path;vector<vector<int>>res;int sum=0;void backtracking(int k,int n,int index){if(sum==n&&path.size()==k)//終止條件{res.push_back(path);return;}for(int i=index;i<=9;i++)樹形結(jié)構(gòu)邏輯{path.push_back(i);sum+=i;backtracking(k, n, i+1);sum-=i;//回溯path.pop_back();}return;}    vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 1);return res;}
};

Leetcode17 電話號碼的字母組合

題目鏈接：17. 電話號碼的字母組合 - 力扣（LeetCode）

代碼隨想錄題解：代碼隨想錄 (programmercarl.com)

思路：這道題目的終止條件和上面三道題幾乎一樣，只不過樹形邏輯要通過一個二維字符串?dāng)?shù)組做一個映射。

代碼：

class Solution {
public:string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};string path;vector<string> res;void backtracking(string a,int index){if(path.size()==a.size())//終止條件{res.push_back(path);return;}int digit=a[index]-'0';//映射string letter=letterMap[digit];for(int i=0;i<letter.size();i++)//樹形結(jié)構(gòu)邏輯{path.push_back(letter[i]);backtracking(a, index+1);path.pop_back();//回溯}return;}vector<string> letterCombinations(string digits) {if(digits.size()==0){return res;}backtracking(digits, 0);return res;}};

總結(jié)

求解回溯模板需要想好終止條件以及樹形邏輯的代碼編寫，不需要仔細思考遞歸邏輯，相比于二叉樹的各種遍歷簡單許多。