找工作准备刷题Day10 回溯算法 (卡尔41期训练营 7.24）

回溯算法今天这几个题目做过，晚上有面试，今天水一水。

第一题：Leetcode77. 组合

题目描述

解题思路

从题目示例来看，k个数是不能重合的，但是题目没有明确说明这一点。

使用回溯算法解决此问题，利用树形结构。

回溯算法终止条件：有了k个数；

遍历过程：由于k个数不能重合，需要使用一个变量来标志遍历从何处开始。

题解

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

优化方式

剪枝：i从遍历到，而不是遍历到 n。这个式子确定方法：假设n为9，k为3，在开始时path为空，第一次遍历是从 1~7,7正好是9-3+1。（说白了，这里只需要举个例子，就能知道n-(k-path,size()）后面需要加个1。

第二题：216. 组合总和 III

题目描述

解题思路

需要从1~9中选出所有 k个不重复组合、k个数字之和为n。

在回溯时，需要目标和n、现在的和 NowSum作为函数参数，还需要startNumber表示遍历开始位置。

题解

class Solution {
public:vector<vector<int>> ans;vector<int> path;vector<vector<int>> combinationSum3(int k, int n) {bT(n, k, 1, 0);return ans;}// targetSum为目标总和，k为数字个数，startNumber为遍历开始数字，NowSum为现在总和void bT(int targetSum, const int k, int startNumber, int NowSum) {if (path.size() == k && targetSum == NowSum) {ans.push_back(path);return;}if (path.size() >= k || NowSum > targetSum)return;for (int i = startNumber; i <= 9 - (k - path.size()) + 1; i++) {path.push_back(i);bT(targetSum, k, i + 1, NowSum + i);path.pop_back();}}
};

技巧

剪枝：当遍历的数字大于等于k 或者现有的数字和已经超过targetSum时，可以不继续遍历（这一步需要在检查数字和为targetSum之后）；i遍历不用从startNumber到9，而是 9-(k-path.size())+1，同第一题，举个例子就行。

回溯技巧：利用函数传值，不用修改NowSum，而是在NowSum+i（雕虫小技）。

第三题：Leetcode17. 电话号码的字母组合

题目描述

解题思路

对于digits的每一位数字，依次遍历即可。需要一个变量标志目前遍历到哪一位。

对于每个数字对应的字母，由于数字是以string形式给定，所以使用unordered_map<char,string>存储。

由于存在digits为0，因此，在调用回溯之前先判断digits。

题解

class Solution {
public:vector<string> ans;string str;unordered_map<char, string> ump;vector<string> letterCombinations(string digits) {if (digits.length() == 0)returnump['2'] = "abc";ump['3'] = "def";ump['4'] = "ghi";ump['5'] = "jkl";ump['6'] = "mno";ump['7'] = "pqrs";ump['8'] = "tuv";ump['9'] = "wxyz";backTracking(digits, 0);return ans;}void backTracking(const string digits, int startIdx) {if (str.length() == digits.length()) {ans.push_back(str);return;}for (int i = 0; i < ump[digits[startIdx]].length(); i++) {str.push_back(ump[digits[startIdx]][i]);backTracking(digits, startIdx + 1);str.pop_back();}}
};