rancho log 回溯算法

---

DFS算法

DFS常用于解决的问题：（1）从图中取出某种符合条件的路径，或判断是否存在某种路径；图中元素的无序的组合、有序的序列问题；（2）二叉树相关；

面试常问：DFS的时间复杂度一般是O(方案数×找到每个方案的时间复杂度)

做题第一步：绘图分析

---

一、回溯/基于图的DFS

基于回溯/分治的处理方法，此处暂不区分。
求取结果集的过程转换为树的生长过程，叶子节点为最终筛选目标。
在树的生长过程中进行剪枝操作。

1.组合问题

★★组合是无序不重复的，{1，2}=={2，1}★★
77. 组合
剪枝优化：数组中剩余元素数量<实际还需要元素数量。
39. 组合总和
40. 组合总和 II
剪枝优化：1、使用标志数组used；2、在当前层排除当前元素与前一位元素相同的情况。
216. 组合总和 III
17.电话号码的字母组合
用字符串数组映射电话号码的关系。

2.排列问题

★★排列是有序的，{1，2} != {2，1}★★
使用标记数组used[]辅助分析。
46.全排列
47. 全排列 II
526
996

3.分割问题

分割后的子串（子序列、子数组等等）大概率需要进行Isvalid判断。
131. 分割回文串（回文串易涉及DP，需要考虑使用DP进行性能优化）
93.复原IP地址（字节一面）

4.子集问题

子集问题求取的是符合条件的所有节点，与上文的组合、排列、分割对叶子节点进行判断不同。
78.子集：不含重复元素的数组，返回所有子集。
90.子集II：包含重复元素的数组，返回所有子集(排除重复)。

5.棋盘问题

51.N皇后问题
37.解数独
扩展：36. 有效的数独：使用哈希表进行九宫格判断（网易后端笔试，六宫格）

6.矩阵中四个方向的搜索

79.单词搜索（阿里笔试）
非常棒的题目！
DFS图的建立，每一个栅格位置都可以作为一个根节点建立DFS

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        //遍历起点
        for(int row = 0  ; row<board.size() ; row++){
            for(int coloum = 0 ; coloum <board[0].size() ; coloum++){
                //由当前点作为起点出发遍历能找到单词
                if(backtracking(board , word , row , coloum ,0)){
                    return true;
                }
                //返回true
            }
        }
        //未找到
        return false;
    }
private:
    bool backtracking(vector<vector<char>>& board , string word , int row ,int coloum , int index)
    {
        //终止条件-单词搜索完成
        if(index==word.size()) return true;

        //四个方向的回溯遍历不用for循环
        bool entry = false;
        if(row >= 0 && row < board.size() && coloum>=0 && coloum<board[0].size() && board[row][coloum]==word[index])
        {
            //建立四个DFS，上下左右四个方向
            ++index;//word递增
            char temp = board[row][coloum];
            board[row][coloum]='0';//标记为已使用

            entry = backtracking(board , word , row+1 , coloum , index);
            if(entry==false) entry = backtracking(board , word , row-1 , coloum , index);
            if(entry==false) entry = backtracking(board , word , row , coloum-1 , index);
            if(entry==false) entry = backtracking(board , word , row , coloum+1 , index);

            index--;
            board[row][coloum]=temp;
        }
        return entry;
    } 
};

212. 单词搜索 II
回溯+前缀树
980. 不同路径 III

二、二叉树的DFS

待补充

总结