博客

LeetCode 216.组合总和III

题目链接：

LeetCode 216.组合总和III

class Solution {
private:
    vector<int> path;
    vector<vector<int>> res; 
    void backtracking(int k,int n,int sum,int startindex)
    {
        if(sum > n)
        return;//剪枝
        if(path.size() == k && sum == n)
        {
            res.push_back(path);
            return;
        }
        for(int i = startindex;i <= 9 - (k-path.size())+ 1;i++)//剪枝
        {
            sum += i;
            path.push_back(i);
            backtracking(k,n,sum,i+1);
            sum -= i;
            path.pop_back();//回溯
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,0,1);
        return res;
    }
};

思路：

回溯三部曲：

确定参数为n(目标和)、k（每个组合大小）、startindex（函数起始位置）、sum（遍历时的累加和）；终止条件：组合大小为目标大小时，将组合存入结果集中；单层逻辑：通过for循环从1到9进行遍历（代码段为加了剪枝操作），存入遍历值i，sum累加；每次进行下一层递归时，起始位置加一，继续遍历。完成一次组合后进行回溯弹出操作。

小结：

剪枝操作中

首先是判断累加和是否超出目标和

，超出则停止遍历；其次减小for循环的范围，

（k – path.size）是还需要的数的个数，9 – （k – path.size）算出遍历的上界，+1调整下标

。

LeetCode 17.电话号码的字母组合

题目链接：

LeetCode 17.电话号码的字母组合

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:
    string s;
    vector<string> res;
    void backtracking(string digits,int index)
    {
        if(s.size() == digits.size())//收集到对应长度的字符停止遍历
        {
            res.push_back(s);
            return;
        }
        int digit = digits[index] - '0';//将数字从string类型转化为int类型
        string letter = letterMap[digit];//找到数字在集合中对应的字符串
        for(int i = 0;i < letter.size();i++)
        {
            s.push_back(letter[i]);
            backtracking(digits,index + 1);
            s.pop_back();//回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        res.clear();
        s.clear();
        if(digits.size() == 0)//特判，数字为空时直接返回
        return res;
        backtracking(digits,0);
        return res;
    }
};

思路：

首先将数字

对应的字母存入一个集合

中，之后

找到每个数字对应的字符串

，用for循环

将字符串中的字符存入结果字符串s

中，进行下一层遍历，最后回溯；当存入的字符长度符合数字长度时，将其存入结果集即可。

小结：

本题中遍历的

深度取决于数字个数，宽度为每个数字所对应的字符串长度

。

隐藏回溯：

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:
    string s;
    vector<string> res;
    void backtracking(string digits,int index,string s)
    {
        if(s.size() == digits.size())//收集到对应长度的字符停止遍历
        {
            res.push_back(s);
            return;
        }
        int digit = digits[index] - '0';//将数字从string类型转化为int类型
        string letter = letterMap[digit];//找到数字在集合中对应的字符
        for(int i = 0;i < letter.size();i++)
        {
            backtracking(digits,index + 1,s + letter[i]);//隐藏回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        res.clear();
        s.clear();
        if(digits.size() == 0)//特判，数字为空时直接返回
        return res;
        backtracking(digits,0,"");
        return res;
    }
};

思路

：

通过用s + letter[ i ]进行遍历，不改变s的值

，可以实现对回溯的隐藏。