代码随想录第22天|回溯part2 组合总和III电话号码的字母组合

本文主要是介绍代码随想录第22天|回溯part2 组合总和III电话号码的字母组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

216.组合总和III

在这里插入图片描述
当组合的数量为k就判断和，并且返回。
在枚举的时候可以进行剪枝，如果总和已经超过了n，那么就没必要继续递归下去了

class Solution {
public:vector<int> path;vector<vector<int>> res;void backTracking(int n, int k, int step, int sum) {if (path.size() == k) {if (sum == n)res.push_back(path);return;}for (int i = step; i <= 9 - (k - path.size()) + 1; i++) {if (sum + i > n)break;path.push_back(i);backTracking(n, k, i + 1, sum + i);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backTracking(n, k, 1, 0);return res;}
};

17.电话号码的字母组合

在这里插入图片描述
递归遍历每个数字，然后根据遍历到的数字来进行枚举即可

class Solution {
public:vector<string> res;string path;void backTracking(unordered_map<char, string>& mp, string digits,int step) {if (digits.size() == 0)return;if (step == digits.size()) {res.push_back(path);return;}string choice = mp[digits[step]];for (int i = 0; i < choice.size(); i++) {path.push_back(choice[i]);backTracking(mp, digits, step + 1);path.pop_back();}}vector<string> letterCombinations(string digits) {unordered_map<char, string> mp;mp['2'] = "abc";mp['3'] = "def";mp['4'] = "ghi";mp['5'] = "jkl";mp['6'] = "mno";mp['7'] = "pqrs";mp['8'] = "tuv";mp['9'] = "wxyz";backTracking(mp, digits, 0);return res;}
};