找工作准备刷题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)
            return
        ump['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();
        }
    }
};