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;}
};
