开始回溯的学习

77. 组合 - 力扣（LeetCode）

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

216. 组合总和 III - 力扣（LeetCode）

class Solution {
public:vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> ans;vector<int>  path; dfs(k, n, ans, path,1);return ans;}private:void dfs(int k, int n, vector<vector<int>>& ans, vector<int>& path, int index){if(path.size() == k && n == 0){ans.push_back(path);return;}for(int i = index; i < 10; i++){path.push_back(i);dfs(k, n -i, ans,path,i+1);path.pop_back();}}
};

17. 电话号码的字母组合 - 力扣（LeetCode）

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