代码随想录打卡—day25—【回溯】

代码随想录打卡—day25—【回溯】— 回溯基础练习 4.14

本文主要是介绍代码随想录打卡—day25—【回溯】— 回溯基础练习 4.14，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 216.组合总和III

216. 组合总和 III

直接常规的dfs，就是在组合的基础上叶子节点进行判断。我的AC版本：

class Solution {
public:vector<vector<int>> ans;vector<int> now;bool vis[10];void dfs(int u,int k,int n,int startidx,int sum){if(sum > n)return;if(u == k){if(sum == n){ans.push_back(now);}return;}for(int i = startidx; i <= 9; i++){if(!vis[i]){vis[i] = 1;now.push_back(i);dfs(u+1,k,n,i + 1,sum + i);vis[i] = 0;now.pop_back();}}}vector<vector<int>> combinationSum3(int k, int n) {dfs(0,k,n,1,0);return ans;}
};

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

17. 电话号码的字母组合

一开始我的dfs里面有vis[]，即每一个字母只可以访问一次，但是过不了比如 "222" 这样测试样例，后来删掉就过了，AC代码：

class Solution {
public:vector<string> ans;string path;string a[10] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void dfs(int u,string digits){if(u == digits.size()){ans.push_back(path);return;}for(int i = 0; i < a[digits[u]-'0'-2].size();i++){char now_char = a[digits[u]-'0'-2][i];int now_char_idx = now_char - 'a';path.push_back(now_char);dfs(u+1,digits);path.pop_back();}}vector<string> letterCombinations(string digits) {if(digits == "")return ans;dfs(0,digits);return ans;}
};