回溯法要点和模板框架

• 有位大佬说：“回溯是递归的副产品，只要有递归就会有回溯。”
• 回溯法可以解决的问题：组合问题、切割问题、子集问题、排列问题、棋盘问题等。
• 回溯法的理解：回溯法可以抽象成树形结构。借用大佬的图：

•  回溯法的模板（伪代码）：

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

    for (选择：本层中集合元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径， 选择列表); // 递归
        回溯，撤销处理结果；
    }
}

　　牢记回溯三部曲：参数，终止条件，单层遍历处理。

• 小试牛刀：力扣77.组合

　　给定两个整数n和k，返回1，2，...，n中所有可能的k个数的组合。套用上面的模板可以得到以下代码：

class Solution {
private:
    vectorint>> ans;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if(path.size() == k) {         // 终止条件
            ans.push_back(path);
            return;
        }
        //for(int i = startIndex; i <= n; i++) { // 控制树的横向遍历
        for(int i = startIndex; i <= n - (k - path.size() + 1); i++) {   // 剪枝优化，后续没必要遍历
            path.push_back(i);         // 处理节点
            backtracking(n, k, i + 1); // 递归：处理树的纵向遍历，下一层搜索从i+1开始
            path.pop_back();           // 回溯，撤销处理的节点
        }
    }
public:
    vectorint>> combine(int n, int k) {
        ans.clear();                   // 非必要
        path.clear();                  // 非必要
        backtracking(n, k, 1);
        return ans;
    }
};

• 力扣216.组合总和III

　　从1-9中找出所有相加和为n的k个数的组合，组合中的元素不允许重复。

　　示例1： 输入k = 3，n = 7；输出：[[1, 2, 4]]；

　　示例2： 输入k = 3, n = 9；输出：[[1, 2, 6], [1, 3, 5], [2, 3, 4]]

　　依旧是利用回溯三部曲：确定递归函数参数、确定种植条件、单层搜索处理。

class Solution {
private:
　　vectorint>> result; 
　　vector<int> path; 
　　void backtracking(int targetSum, int k, int sum, int startIndex) {
　　　　if (path.size() == k) {
　　　　　　if (sum == targetSum) result.push_back(path);
　　　　　　return;
　　　　}
　　　　for (int i = startIndex; i <= 9; i++) {
　　　　　　sum += i; // 处理
　　　　　　path.push_back(i); // 处理
　　　　　　backtracking(targetSum, k, sum, i + 1); // index调整位置
　　　　　　sum -= i; // 回溯
　　　　　　path.pop_back(); // 回溯
　　　　}
　　}
public:
　　vectorint>> combinationSum3(int k, int n) {
　　　　backtracking(n, k, 0, 1);
　　　　return result;
　　}
};

• 17.电话号码与字母组合

　　本题多了一个步骤：写有数字的字符串（string）→按键上的数字（int）→数字对应的字符串（string）

　　这个地方需要注意的是需要先完成数字和字母映射，才能取出对应的字符串，很容易犯迷糊怎么写。

class Solution {
private:
    // 使用map或定义一个数组，完成数字和字母的映射
    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;   // s表示收集叶子节点的结果

    void backtracking(const string& digits, int index) { // index表示遍历的第几个数字
        //终止条件
        if(s.size() == digits.size()) {                     // index同时也表示树的深度
            result.push_back(s);
            return;
        }

        // 将题目所给字符串中的数字转换成int，然后将数字按键对应的字符串取出来
        // 本题中的字符串在不同集合中
        int digit = digits[index] - '0';    // 将index指向的数字转换成int
        string letters = letterMap[digit];  // 取数字对应的字符集

        // for循环实现单层遍历
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);
            backtracking(digits, index + 1);
            s.pop_back();
        }
    }

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

• 39.组合总和

　　给定一个无重复的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数组可以无限制重复选取。

class Solution {
public:
    vectorint>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum > target) return;
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 关键点：不用i+1表示可以重复读取当前的数
            sum -= candidates[i];
            path.pop_back();
        }
    }

    vectorint>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

• 40.组合总和II

// 需要结合图去理解
class Solution {
private:
    vectorint>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // 对同一树层使用过的元素进行跳过
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i-1] == false) {
                continue;
            }
            // 以调用递归函数对称，成反向操作，即回溯
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used);
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vectorint>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        // 首先进行排序，让其相同的元素挨在一起
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }


};