理论基础

回溯是递归的副产品，只要有递归就会有回溯。回溯函数也就是递归函数，指的都是一个函数。
回溯法并不是什么高效的算法。回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。
如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

回溯法解决的问题–>排列组合

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

框架模板

void backtracking(路径，参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (nextnodes) {
        //处理节点;
        backtracking(路径，参数); // 递归
        //回溯，撤销处理结果
    }
}

1、77组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。

我的思路：没做出来。。一开始我直接使用 递归/回溯 框架，但是结果有重复，如何去重？

代码随想录：可以剪枝优化。对于递归的最后几个元素构不成组合。

//一般的排问题迭代框架
for(i = 1;i<...)
    for(j = 1;j<...)
        for(k = 1;k<...)
        i!=j j!=k

//一般的组合问题迭代框架，不走回头路
for(i = 1;i<...)
    for(j = i+1;j<...)
        for(k = j+1;k<...)
//组合+剪枝
for(i = 1;i<len-k ...)
    for(j = i+1;j<len-k+1 ...)
        for(k = j+1;k<len-k+2 ...)
        ...
        for(k = j;k<len ...)

// 看了代码随想录后我写的，未剪枝
class Solution {
public:
    void traverse(vector<int> &rec, int dep,int k, int startidx, int endidx, vector<int> &path,vector<vector<int>> &res){
        if(dep == k){ //截止条件
            res.emplace_back(path);
            return;
        }
        for(int i = startidx;i<=endidx-k+dep+1;i++){
            path.emplace_back(rec[i]);
            traverse(rec,dep+1,k,i+1,endidx,path,res);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> rec;
        for(int i = 1;i<=n;i++){
            rec.emplace_back(i);
        }
        vector<int> path;
        vector<vector<int>> res;
        path.reserve(k);
        traverse(rec,0,k,0,rec.size()-1,path,res);
        return res;
    }
};
//剪枝
class Solution {
public:
    void traverse(vector<int> &rec, int dep,int k, int startidx, int endidx, vector<int> &path,vector<vector<int>> &res){
        if(dep == k){ //截止条件
            res.emplace_back(path);
            return;
        }
        for(int i = startidx;i<=endidx-k+dep+1;i++){
            path.emplace_back(rec[i]);
            traverse(rec,dep+1,k,i+1,endidx,path,res);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> rec;
        for(int i = 1;i<=n;i++){
            rec.emplace_back(i);
        }
        vector<int> path;
        vector<vector<int>> res;
        path.reserve(k);
        traverse(rec,0,k,0,rec.size()-1,path,res);
        return res;
    }
};

2、216组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

我的思路： 和上一题一样。只需在截止条件处进行判断即可。
代码随想录

class Solution {
public:
    void traverse(vector<int> &rec, int dep,int k, int startidx, int endidx, vector<int> &path,int sum, int n, vector<vector<int>> &res){
        if(dep == k){ //截止条件
            if(sum == n){
                res.emplace_back(path);
            }
            return;
        }
        for(int i = startidx;i<=endidx-k+dep+1;i++){
            path.emplace_back(rec[i]);
            traverse(rec,dep+1,k,i+1,endidx,path,sum+rec[i],n,res);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> rec;
        for(int i = 1;i<=9;i++){
            rec.emplace_back(i);
        }
        vector<int> path;
        vector<vector<int>> res;
        path.reserve(k);
        traverse(rec,0,k,0,rec.size()-1,path,0,n,res);
        return res;
    }
};

3、17电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

我的思路：一开始还愣了一下，思路有点不清晰。这道题关键在于8个按键的字母是独立的，所以不用关心重复问题。
代码随想录

小总结：遇到这种题有点模糊啊的话，就直接先用迭代for写出来框架，然后再用递归整理。

for(str[0]的元素 )
    for(str[1]的元素 )
        for(str[2]的元素 )
        ...

// 我的
class Solution {
public:
    void traverse(vector<string> &res,string &path,int depth, string &digits,unordered_map<char,string> &mem){
        if(depth == digits.size()){
            res.emplace_back(path);
            return;
        }
        int len = (digits[depth]=='7'||digits[depth]=='9')?4:3;
        for(int i = 0;i<len;i++){
            path+=mem[digits[depth]][i];
            traverse(res,path,depth+1, digits,mem);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)return vector<string>();
        unordered_map<char,string> mem={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},
                                    {'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
        vector<string> res;
        string path;
        traverse(res,path,0, digits,mem);
        return res;
    } 
};

//代码随想录
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 s;
    void backtracking(const string& digits, int index) {
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';        // 将index指向的数字转为int
        string letters = letterMap[digit];      // 取数字对应的字符集
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);            // 处理
            backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了
            s.pop_back();                       // 回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};