代码随想录–回溯部分

day 22 回溯部分第一天

---

---

回溯算法基础知识

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

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

---

一、力扣77–组合

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

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

输出的结果应该有$C_n^k$个组合，最粗暴的方法就是一层一层去套循环，但是如果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
	}
}