总的链接 :
面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
17 . 电话号码的字母组合
1 . 先创建一个下标 与 对应字符串映射的数组，这里使用hash表进行映射也是可以的 ；
2 . 对于回溯 ， 如果到了叶子节点 ， 那么就直接添加即可 ， 对于每一个path[i],都是存放digits[i]中数字字符对应字符串中的一个字符 ， 遍历该字符串 ， 对每一个字符进行递归操作 ；
3 . 对于不用恢复现场 : 因为每次递归到 i，一定会修改 path【i】，那么递归到终点时，每个 path【i】 都被覆盖成要枚举的字母，所以不需要恢复现场。
class Solution {
string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
vector<string> letterCombinations(string digits) {
int n = digits.length();
if (n == 0) return {};
vector<string> ans;
string path(n, 0); // 本题 path 长度固定为 n
function<void(int)> dfs = [&](int i) {
if (i == n) {
ans.emplace_back(path);
return;
}
for (char c : MAPPING[digits[i] - '0']) {
path[i] = c; // 直接覆盖
dfs(i + 1);
}
};
dfs(0);
return ans;
}
};
77 . 组合
. - 力扣（LeetCode）
枚举下一个选那个!
void dfs(int n , int k , int idx) ;
idx确定选取元素不重复 ;
如果当前集合中元素个数==k , 那么加入到ans中 ；
枚举下 一 个数选谁 ，从idx开使 ， 遍历到n ;
class Solution {
public:
vector<vector<int>> ans;//存放符合条件结果的集合
vector<int> path;//用来存放符合条件的结果
void dfs(int n,int k,int startIndex){
if(path.size()==k){
ans.push_back(path);
return;
}
for(int i=startIndex;i<=n-(k-path.size())+1;i++){
path.push_back(i);//处理节点
dfs(n,k,i+1);//递归
path.pop_back();//回溯，撤销处理的节点
}
}
vector<vector<int>> combine(int n, int k) {
dfs(n,k,1);
return ans;
}
};枚举这个数选或不选 :
class Solution {
public:
vector<vector<int>> ans ;
vector<int> path ;
void dfs(int n , int k , int idx){
int sz = path.size() ;
if(sz == k){
ans.push_back(path) ;
return ; // 回溯
}
if(k-sz>n-idx+1) return ;
// 不选
dfs(n,k,idx+1) ;
// 选
path.push_back(idx) ;
dfs(n,k,idx+1) ;
path.pop_back() ;
}
vector<vector<int>> combine(int n, int k) {
dfs(n , k , 1);
return ans ;
}
};46 . 全排列
设置一个used数组 ， 来表示当前数用没用过 ， 没用过才能遍历 ；
每次都需要从 0 到 nums.size() 访问 ；
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backtrack(vector<int>nums,vector<bool> used){
if(path.size() >= nums.size()){
ans.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(used[i]==true) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack(nums,used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
ans.clear();
path.clear();
vector<bool> used(nums.size(),false);
backtrack(nums,used);
return ans;
}
};39 . 组合总和
按照target能不能够减到0来进行暴力寻找 :
class Solution {
public:
vector<vector<int>> ans ;
vector<int> path ;
int n ;
void dfs(vector<int>& c, int target , int idx){
if(target == 0){
ans.push_back(path) ;
return ;
}
if(target < 0){
return ;
}
// 枚举下一个选哪个
for(int i=idx;i<n;i++){
path.push_back(c[i]);
dfs(c,target-c[i],i);// 能重复选取
path.pop_back() ;// 撤销
}
}
vector<vector<int>> combinationSum(vector<int>& c, int target) {
n = c.size() ;
sort(c.begin(),c.end()) ;
dfs(c , target , 0);
return ans ;
}
};52 . N皇后 ||
直接用一个 col 数组 ，来存每一行存那一列的存皇后的位置 ;
然后在回溯的时候，将与前面不冲突的数加入集合 ;
22 . 括号生成
. - 力扣（LeetCode）
枚举填左括号还是右括号
class Solution {
public:
vector<string> generateParenthesis(int n) {
int m = n * 2;
vector<string> ans;
string path(m, 0);
function<void(int, int)> dfs = [&](int i, int open) {
if (i == m) {
ans.emplace_back(path);
return;
}
if (open < n) { // 可以填左括号
path[i] = '(';
dfs(i + 1, open + 1);
}
if (i - open < open) { // 可以填右括号
path[i] = ')';
dfs(i + 1, open);
}
};
dfs(0, 0);
return ans;
}
};79 . 单词搜索
. - 力扣（LeetCode）
对每一个起点进行dfs搜索 ， 判断是否满足 ;
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int n = board.size();
int m = board[0].size();
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool st[n][m];
function<bool(int,int,int)> dfs = [&](int x,int y,int k)->bool{
if(k==word.size()) return true;
bool flag = false;
st[x][y] = true;
for(int i=0;i<4;i++){
int tx = x+dx[i];
int ty = y+dy[i];
if(tx>=0 && tx<n && ty>=0 && ty<m && board[tx][ty] == word[k] && !st[tx][ty]) {
//cout<<tx<<" "<<ty<<" "<<k<<endl;
if(dfs(tx,ty,k+1)){
flag = true;
break;
}
}
}
st[x][y] = false;
return flag;
};
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) {
if(board[i][j] == word[0]){
memset(st,0,sizeof st);
if(dfs(i,j,1)){
return true;
}
}
}
return false;
}
};
