DFS 回溯 - wenzhoullq/leetcode GitHub Wiki
- 数组长度
给予的数组的长度<=30即可用回溯（最为重要）,针对的是非全排列；如果是全排列的话，那么length<=10，但是如果是记忆化DFS可以放阔数组条件到30.
- 不可出现重复
主函数Array.sort()，然后每次dfs()后使用while(i+1<nums.length&&nums[i]==nums[i+1]) i++;去重
- 递归
void dfs(int index,int target){
if(target==0){
ans.add(new LinkedList(temp));
return ;
}
if(index==len) return ;
dfs(index+1,target);
if(满足题意){
dfs(index+1,target-nums[index]);//下标的变化根据题意来,如果是全排列的话index+1变为0
}
}- 非递归,二进制枚举
int n = str.length();
for(int i = 1; i < (1<<n); i++){
int x = 0;
Integer.numberOfTrailingZeros(i);//代表被枚举的位置
for(int j = i ; j > 0 ; j = (j - 1) & i){
x = 具体运算;
}
//处理
}适用于绝大部分的回溯题
301. 删除无效的括号 (括号左右来回求可以匹配的左右括号最大值，然后选最大值的最小值作为target)
回溯的最大是15,如果是30可以考虑折半回溯,即对前面取一半对后面取一半
805. 数组的均值分割 细节比较多,一个是总的平均数和子数组的平均值一样,一个是转为求0即对全部的值-sum，另一个是可能会出现double,因此对每个数*len处理,最后一个是sum=0时候的特殊判断
if(index==nums.length){
ans.add();
return ;
}
temp.add();
dfs(index+1,temp);//加入本次index所对应的值
temp.remove(temp.size()-1);
dfs(index+1,temp);//不加入本次index所对应的值对于一个数组挑几个构成组合是可以使用的，但是对于重复选择某一个下标题是不可以使用 严格来说，它并不是回溯，而是dfs
direct回溯最主要在于对四个方向回溯
if(y<0||y==lengthy||x<0||x==lengthx||visit[y][x]) return false;
visit[y][x]=true;
temp.append(board[y][x]);
if(满足要求){
add()
return true;
}
for(int i=0;i<4;i++){//四个方向探索
int tempy=y+direct[i][0],tempx=x+direct[i][1];
if(backtrack(tempy,tempx)) return true;
}
//删除本次结果，回溯退回
visit[y][x]=false;存在性dfs是boolean,甚至还可以剪枝
212. 单词搜索 II 可以使用字典树剪枝
int dfs(int y,int x,int ans){
if(y<0||y==lengthy||x==lengthx||x<0||grid[y][x]==0||visit[y][x]) {
return 0;
}
ans+=grid[y][x];
// System.out.print(ans+" ");
visit[y][x]=true;
int temp=0;
for(int i=0;i<4;i++){
temp=Math.max(temp,dfs(y+direct[i][0],x+direct[i][1],0));
}
visit[y][x]=false;
return ans+temp;
}
main(){
for(int i=0;i<lengthy;i++){
for(int j=0;j<lengthx;j++) {
ans=Math.max(dfs(i,j,0),ans);
}
}
}主要在于temp的设定和temp的求值以及ans的比较
1020. 飞地的数量与普通的direct不同的是，它是从边缘开始访问，访问所有能访问的点
class Solution {
int leny,lenx;
int[][] coach;
public int main() {
leny=matrix.length;
lenx=matrix[0].length;
int ans=0;
for(int i=0;i<leny;i++){
for(int j=0;j<lenx;j++){
ans=Math.max(ans,dfs(i,j,-1));
}
}
return ans;
}
int dfs(int y,int x){
if(y<0||y==leny||x<0||x==lenx) return 0;
int sum=0;
sum=Math.max(dfs(y+1,x)+1,sum);//长度型的精髓在于这个+1
sum=Math.max(dfs(y-1,x)+1,sum);
sum=Math.max(dfs(y,x+1)+1,sum);
sum=Math.max(dfs(y,x-1)+1,sum);
coach[y][x]=sum;
return sum;
}
}没有很好的归给，于是放到其他里
boolean backtrack(int y,int x){
if(){
if(){
//x和y的移动
}
else return true;
}
if(不满足) {
if(backtrack(y,x+1)) return true;
}
else{
for(){
if(check(y,x,j)) continue;
//设置访问
//添加
if(backtrack(y,x+1)) return true;
//取消访问
//删除
}
}dfs是boolean型，因为没有方向数组，难点在于y和x的移动，终止条件，check函数
37. 解数独(状态压缩)
51. N 皇后 对于八皇后而言，可以简化这个模板，降低递归次数
797. 所有可能的路径 构图类dfs
同行同列为相邻，而非邻接为相邻
与其他回溯不同的是，它是通过i和j确定截取部分而不是一个个添加判断是否匹配。
void dfs(int index){
if(index==len()) {
ans.add(new LinkedList<String>(temp));
return ;
}
for(int i=index;i<len;i++){
String str=s.substring(index,i+1);
if(判断是否满足题意) continue;
temp.add(str);
backtrack(i+1);
temp.removeLast();
}
}211. 添加与搜索单词 - 数据结构设计 字典树的dfs，值得注意的是，字典树中顺着查也是dfs
753. 破解保险箱(hs去重
987. 二叉树的垂序遍历 多条件排序用优先队列
1255. 得分最高的单词集合状态压缩
1766. 互质树 如何计算互质是重点，以及数据过多，先存储互质数
2212. 射箭比赛中的最大得分(数据大小为12,因此dfs)