17.给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
分析：
1.返回‘所有组合’意味着回溯
2.数字和对应的串用哈希表存储
3.回溯结构，结，选，剪，选，下，出
class Solution {
public:
vector res;
string conbination;
unordered_map phoneMap{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
vector letterCombinations(string digits) {
if(digits.empty()) return res;
backtrace(res,conbination,digits,0);
return res;
}
//参数：结果，中间结果，原数据，起点
void backtrace(vector& res, string& conbination, const string digits, int start){
//什么时候结束要清楚，需要先模拟一下
if(start == digits.length()){
res.push_back(conbination);
}
else{
char digit = digits[start];
string letters = phoneMap.at(digit);
for(const auto& letter:letters){
//if(letter==conbination.back()) break;
conbination.push_back(letter);
backtrace(res,conbination,digits,start+1);
conbination.pop_back();
}
}
}
};
37判断数独
1.回溯函数中访问下一个位置，要判断是不是结束了，不然会越界
2.后三步都要在当前数字填入后不会没有错误的条件下进行，也就是ifvalid下执行，否则越界
class Solution {
public:
void solveSudoku(vector>& board) {
backtrace(board);
}
bool backtrace(vector>& board){
for(int i=0;i
for(int j=0;j//选
if(board[i][j]!='.') continue; //剪
for(char k='1';k<='9';k++){
if(isvalid(i,j,k,board)){
board[i][j] = k; //选
if(backtrace(board)) return true; //下一个位置
board[i][j]='.'; //回溯
}
}
return false;
}
}
return true;
}
bool isvalid(int row,int col,char val,vector>& board){
for(int i=0;i<9;i++){
if(board[row][i]==val) return false;
}
for(int j=0;j<9;j++){
if(board[j][col]==val) return false;
}
int startrow = (row/3)*3;
int startcol = (col/3)*3;
for(int i =startrow;i
for(int j=startcol;j
if(board[i][j]==val) return false;
}
}
return true;
}
};
36.组合总数
1.结束的两个条件
2.如何剪枝
class Solution {
public:
vector> res;
vector conbination;
vector> combinationSum(vector& candidates, int target) {
backtrcking(res,conbination,0,candidates,target);
return res;
}
void backtrcking(vector>& res,vector& conbination,int start,vector& candidates, int target){
if(target==0){
res.push_back(conbination);
}
else{
for(int i=start;i
if(target-candidates[i]<0) continue;
conbination.push_back(candidates[i]);
backtrcking(res,conbination,i,candidates,target-candidates[i]);
conbination.pop_back();
}
}
}
};
40.组合2
重点1.如何去重：set函数低效，排序+判断
2.公共变量 就不要加在回溯函数中了
3.结束：题解结果是否符合条件，剪枝：包含访问变量的处理
class Solution {
public:
vector> res;
vector combination;
vector> combinationSum2(vector& candidates, int target) {
sort(candidates.begin(),candidates.end());
backtracking(0,candidates,target);
return res;
}
void backtracking(int start,vector& candidates,int target){
if(target==0){
res.push_back(combination);
}
else{
for(int i=start;i
if(target-candidates[i]<0) break;
if(i>start&&candidates[i]==candidates[i-1]) continue;
combination.push_back(candidates[i]);
backtracking(i+1,candidates,target-candidates[i]);
combination.pop_back();
}
}
}
};
90.给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列
1.去重
2.进入下一层是i+1而不要用start+1
class Solution {
public:
vector> res;
vector combination;
vector> subsetsWithDup(vector& nums) {
sort(nums.begin(),nums.end());
backtracking(0,nums);
return res;
}
void backtracking(int start, vector& nums){
res.push_back(combination);
for(int i=start;i
if(i>start&&nums[i]==nums[i-1]) continue;
combination.push_back(nums[i]);
backtracking(i+1,nums);
combination.pop_back();
}
}
};
131.给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串
1.结束条件-画出递归图
2.剪枝==条件下进行回溯
class Solution {
public:
vector> res;
vector combination;
vector> partition(string s) {
backtracking(s,0);
return res;
}
void backtracking(string s,int start){
if(start==s.size()){
res.push_back(combination);
}
for(int i=start;i
if(isValid(s,start,i)){
combination.push_back(s.substr(start, i-start+1));
backtracking(s,i+1);
combination.pop_back();
}
}
}
bool isValid(string s,int l,int r){
if(s.size()==0) return false;
while(l
if(s[l]!=s[r]) return false;
else{
l++;
r--;
}
}
return true;
}
};
306.累加数，一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。
1.本题判断3子串之间的关系，每个子串判断则可以进行剪枝当前子串的首位如果是0，则需要跳过
2.判断类型的，进入下一层时就可以直接return
3.获取所有子串
class Solution {
public:
vector res;
string temp;
bool isAdditiveNumber(string num) {
return bt(num,0);
}
bool bt(string num,int start){
if(start==num.size()){
if(res.size()>=3) return true;
else return false;
}
for(int i=start;i
temp = num.substr(start, i+1-start);
int n=res.size();
if(temp[0]=='0'&& temp.size()!=1) break;
if(n<2 || stold(temp)-res[n-1]==res[n-2] ){
res.push_back(stold(temp));
if(bt(num,i+1)) return true;
res.pop_back();
}
}
return false;
}
};
797.给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
1.图的表示：邻接表，graph[i]表示某一行中元素
2.对于邻接表的访问，下一层的表示时当前访问的元素值
class Solution {
public:
vector> res;
vector path;
vector> allPathsSourceTarget(vector>& graph) {
path.push_back(0);
bt(graph,0);
return res;
}
void bt(vector>& graph, int start){
int len = graph.size();
if(start==len-1){
res.push_back(path);
}
for(const auto& x:graph[start]){
path.push_back(x);
bt(graph,x);
path.pop_back();
}
}
};
1219 黄金矿工
1.暴力获取每个不为0的起点可以获取的最大值，bt获取每个点可能获取的最大值
2.要获取最大值就要有max操作，值得注意的是bt中求解max为当前值+以下一个值为起点的最大值
3.每个点需要向其上下左右探索，主要操作有
int dir[4]={0,1,0,-1};
for(int i=0;i<4;i++){
int nx=x+dir[i], ny=y+dir[(i+1)%4];
这两步完成；右，下，左，上顺序的探索
4.通过访问数组进行回溯，来控制是否访问过
class Solution {
public:
bool visit[20][20];
int res=0;
int dir[4]={0,1,0,-1};
int m,n;
int getMaximumGold(vector>& grid) {
m=grid.size();
n=grid.at(0).size();
for(int i=0;i
for(int j=0;j
if(grid[i][j]!=0){
visit[i][j]=true;
res=max(res,bt(grid,i,j));
visit[i][j]=false;
}
}
}
return res;
}
int bt(vector>& grid,int x,int y){
int res=grid[x][y];
for(int i=0;i<4;i++){
int nx=x+dir[i], ny=y+dir[(i+1)%4];
if(nx<0||nx>=m||ny<0||ny>=n||!grid[nx][ny]||visit[nx][ny]) continue;
visit[nx][ny] = true;
res=max(res,grid[x][y]+bt(grid,nx,ny));
visit[nx][ny] = false;
}
return res;
}
};
剑指 Offer 38. 字符串的排列
1.组合问题如何解决， if(i>=1&&s[i]==s[i-1]&&!used[i-1]) continue;//判断当前元素是否和上一个元素相同？如果相同，再判断上一个元素是否能用
class Solution {
public:
vector res;
string path;
vector permutation(string s) {
vector used(s.size());
sort(s.begin(),s.end());
bt(s,used);
return res;
}
void bt(string s,vector& used){
if(path.size()==s.size()){
res.push_back(path);
}
for(int i=0;i
if(!used[i]){
if(i>=1&&s[i]==s[i-1]&&!used[i-1]) continue;//判断当前元素是否和上一个元素相同？如果相同，再判断上一个元素是否能用
used[i]=true;
path.push_back(s[i]);
bt(s,used);
used[i]=false;
path.pop_back();
}
}
}
};
