代码随想录算法训练营day22

代码随想录算法训练营

—day22

前言

今天是算法营的第22天，希望自己能够坚持下来！
今日任务：
● 回溯算法理论基础
● 77. 组合
● 216.组合总和III
● 17.电话号码的字母组合

回溯算法理论基础

文章讲解

• 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
• 回溯是递归的副产品，只要有递归就会有回溯。
• 回溯的本质是穷举，是一种纯暴力的方法，嵌套多个for循环 回溯法解决的问题都可以抽象为树形结构
• 回溯的递归函数一般叫backtracking，返回值一般为void，参数比较多，没那么容易确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

回溯法解决的问题

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

回溯法模板

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

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

一、77. 组合

题目链接
文章讲解
视频讲解

思路：

1. 递归函数的参数和返回值：参数：n，k，startIndex（每一层递归需要避开已经遍历过的数，所以需要一个索引去记录遍历到[1,n]的那个数字了）
2. 终止条件：存下来的path大小已经满足k了
3. 单层递归的逻辑：for循环遍历[1,n]，添加单个数字到path中，再递归添加下一个数字（startIndex+1）。
4. 剪枝：其实单层遍历的时候不需要遍历满[1,n]，当遍历到剩下的数字个数已经不足以组成k个的时候已经不需要再遍历了，所以在for循环中，使用i < n - (k - 目前存的个数) + 1，这里+1是因为范围包含了startIndex

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;

    void backtracking(int n, int k, int startIndex) {
        //当组合大小满足k时放入结果集
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        //遍历[1,n]依次寻找结果集, 遍历到剩余元素个数不足以满足k的时候就可以停了
        for (int i = startIndex; i <= n - (k - path.size()) + 1;  i ++) {
            path.push_back(i); //放入i
            backtracking(n, k, i + 1); //寻找跟i能满足k的组合，并且传入遍历的起始下标
            path.pop_back(); //取出i
        }
        return;
    }

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

二、216. 组合总和 III

题目链接
文章讲解
视频讲解

跟77. 组合 其实就是多了个和的约束，思路是差不多的。并且要注意题目说只用数字1到9。

思路：

1. 递归函数参数以及返回值：参数：n，k，startIndex（每一层递归需要避开已经遍历过的数，所以需要一个索引去记录遍历到[1,n]的那个数字了）
2. 终止条件：path大小满足k的时候终止，判断总和是否为n，是则加入结果集。
3. 单层处理逻辑：for循环遍历[1,9]，添加单个数字到path中，再递归添加下一个数字（startIndex+1）。
4. 剪枝：跟77. 组合 一样，for循环中只需要到i < n - (k - 目前存的个数) + 1，并且总和大于n了也可以直接返回，不需要再遍历了。

代码如下：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;

    void backtracking (int k, int n, int sum, int startIndex) {
        if (sum > n) return; //剪枝，超过目标总和了直接返回

        if (path.size() == k) { //组合大小满足的就要返回，没必要继续下去了
            if (sum == n) result.push_back(path); //组合大小满足，总和也满足才加入结果集
            return;
        }

        //遍历[1,n]依次寻找结果集, 遍历到剩余元素个数不足以满足k的时候就可以停了，题目要求只使用数字19
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i ++) {
            sum += i;
            path.push_back(i);
            backtracking(k, n, sum, i + 1);//寻找跟i能满足k的组合，并且传入遍历的起始下标和目前的总和
            path.pop_back();
            sum -= i;
        }

        return;
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 0, 1);
        return result;
    }
};

三、17. 电话号码的字母组合

题目链接
文章讲解
视频讲解

思路：
需要有一个数组来存下每个数字对应的字母，用一个string[]，用下标对应数字，string对应字符串。

递归思路：

1. 递归函数参数以及返回值：参数：digits，Index（这个索引是告诉递归函数遍历到了digits的那个数字）
2. 终止条件：当遍历完digits时终止，将目前存的string放入结果集。
3. 单层处理逻辑：for循环遍历digits[Index]对应的字符串，添加单个字母到string中，再递归添加下一个数字对应的字母（index+1）。

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 (string &digits, int index) {
        if (index == digits.size()) { //当遍历完digits字母时终止并保存结果
            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因为下一层是处理digits的下一个字母了
            s.pop_back(); //回溯
        }
    }

    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        
        if (digits.size() == 0) return result;

        backtracking(digits, 0);
        return result;
    }
};

总结

今天主要学习了回溯算法的理论和其中解决组合类的题目。

• 回溯算法是一种纯暴力的方法，嵌套多个for循环
• 回溯法解决的问题都可以抽象为树形结构
• 组合类的题目需要使用一个索引去告诉函数遍历到哪里了

明天继续加油！