代码随想录打卡第二十二天

代码随想录–回溯部分

day 22 回溯部分第一天


文章目录

  • 代码随想录--回溯部分
  • 回溯算法基础知识
  • 一、力扣77--组合
  • 二、力扣216--组合总和Ⅲ
  • 三、力扣17--电话号码的字母组合
  • 总结


回溯算法基础知识

代码随想录知识链接:代码随想录

本质上回溯法就是暴力搜索法,理解困难且并不高效


一、力扣77–组合

代码随想录题目链接:代码随想录

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

输出的结果应该有 C n k C_n^k Cnk个组合,最粗暴的方法就是一层一层去套循环,但是如果k数量上去了,那就没法去套循环了

回溯法的目的就是解决这个循环没法手写的问题

在这里插入图片描述

实际上有这个图的话,代码就好写很多了

每次递归传入切割后还可以选的数组,以及目前组合的长度,当组合长度为k时就退出这次搜索,进行回溯

代码如下:

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backTracking(int k, int n, int startIndex)
    {
        if(path.size() == k)
        {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i <= n; i ++)
        {
            path.push_back(i);
            backTracking(k, n, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backTracking(k, n, 1);
        return result;
    }
};

二、力扣216–组合总和Ⅲ

代码随想录题目链接:代码随想录

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

和组合的思维一样,用path记录本次回溯过程冲的变量,判断加起来是不是n

代码如下:

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backTracking(int k, int n, int startIndex)
    {
        if(path.size() == k)
        {
            int sum = 0;
            for(auto ele : path) sum += ele;
            if (sum == n) result.push_back(path);
            return;
        }
        for(int i = startIndex; i <= 9; i ++)
        {
            path.push_back(i);
            backTracking(k, n, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        // if(n < (k + 1) * 2) return {};
        backTracking(k, n, 1);
        return result;
    }
};

三、力扣17–电话号码的字母组合

代码随想录题目链接:代码随想录

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回

实际上如果理解了回溯模板的使用,这个题的难度就骤降了

每次遍历本次回溯时数字代表的字符串即可,挨个试

代码如下:

class Solution {
public:
    vector<string> result;
    string path;
    string getChar(int num)
    {
        switch(num)
        {
            case 2: return "abc";
            case 3: return "def";
            case 4: return "ghi";
            case 5: return "jkl";
            case 6: return "mno";
            case 7: return "pqrs";
            case 8: return "tuv";
            case 9: return "wxyz";
            default: return "";
        }
    }
    void backTracking(string digits, int index)
    {
        if(index == digits.size())
        {
            if(!path.empty())result.push_back(path);
            return;
        }
        string s = getChar(digits[index]-'0');
        for(int i = 0; i < s.size(); i++)
        {
            path.push_back(s[i]);
            backTracking(digits, index + 1);
            path.erase(path.end() - 1);
        }
    }
    vector<string> letterCombinations(string digits) {
        backTracking(digits, 0);
        return result;
    }
};

总结

回溯法一般可用模板:

void backTracking()
{
	if(Ending condition)
	{
		// processing
		return;
	}
	for(auto ele : sequence) // Breadth Search
	{
		// push this time
		backTracking();
		// pop this time
	}
}
上一篇:Vue的import什么时候用大括号


下一篇:【机器学习】Exam3