【每日算法】Day 9-1：深度优先搜索（DFS）算法精讲——排列组合与路径问题的终极解法（C++实现）

解锁回溯与遍历的核心能力！今日深入解析深度优先搜索（DFS）的实现原理与优化技巧，结合排列组合、路径搜索等高频场景，彻底掌握递归与剪枝的底层逻辑。

一、DFS 核心思想

深度优先搜索（DFS） 是一种优先探索分支路径到底层的算法，核心特性：

1. 递归/栈驱动：通过递归调用栈或显式栈实现深度遍历

2. 路径探索：适合寻找所有可能解或连通性检测

3. 回溯机制：通过状态重置实现多路径搜索

适用场景：

• 排列组合问题（全排列、子集）

• 矩阵/图中的路径搜索（岛屿问题、迷宫问题）

• 树形结构遍历（路径总和、二叉树操作）

二、DFS 算法模板

1. 递归模板（隐式栈）

void dfs(参数列表) {
    if (终止条件) { 
        记录结果; 
        return; 
    }
    for (选择 in 选择列表) {
        处理选择;    // 前序操作
        dfs(新参数); // 递归进入下一层
        撤销选择;    // 后序操作（回溯）
    }
}

2. 迭代模板（显式栈）

void dfsIterative(Node* root) {
    stack<Node*> stk;
    unordered_set<Node*> visited;
    stk.push(root);
    
    while (!stk.empty()) {
        Node* curr = stk.top(); stk.pop();
        if (visited.count(curr)) continue;
        visited.insert(curr);
        
        // 处理当前节点
        for (auto& neighbor : curr->neighbors) {
            stk.push(neighbor); // 按逆序入栈保证顺序
        }
    }
}

三、四大高频应用场景

场景1：全排列问题（LeetCode 46）

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    function<void(int)> dfs = [&](int start) {
        if (start == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); ++i) {
            swap(nums[start], nums[i]); // 选择当前位
            dfs(start + 1);             // 递归后续位
            swap(nums[start], nums[i]); // 撤销选择
        }
    };
    dfs(0);
    return res;
}

场景2：岛屿数量（LeetCode 200）

int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

void dfs(vector<vector<char>>& grid, int x, int y) {
    if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != '1') 
        return;
    
    grid[x][y] = '0'; // 标记为已访问
    dfs(grid, x + 1, y);
    dfs(grid, x - 1, y);
    dfs(grid, x, y + 1);
    dfs(grid, x, y - 1);
}

场景3：路径总和 III（LeetCode 437）

int pathSum(TreeNode* root, int targetSum) {
    unordered_map<long, int> prefix; // 前缀和计数
    prefix[0] = 1; // 初始前缀和为0出现1次
    int count = 0;
    
    function<void(TreeNode*, long)> dfs = [&](TreeNode* node, long currSum) {
        if (!node) return;
        currSum += node->val;
        // 查找当前路径是否存在前缀和满足 currSum - targetSum
        count += prefix[currSum - targetSum];
        
        prefix[currSum]++; // 记录当前前缀和
        dfs(node->left, currSum);
        dfs(node->right, currSum);
        prefix[currSum]--; // 回溯
    };
    
    dfs(root, 0);
    return count;
}

场景4：组合总和（LeetCode 39）

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> path;
    sort(candidates.begin(), candidates.end());
    
    function<void(int, int)> dfs = [&](int start, int sum) {
        if (sum == target) {
            res.push_back(path);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (sum + candidates[i] > target) break; // 排序后剪枝
            path.push_back(candidates[i]);
            dfs(i, sum + candidates[i]); // 允许重复选择
            path.pop_back();
        }
    };
    
    dfs(0, 0);
    return res;
}

四、DFS 优化技巧

五、大厂真题实战

真题1：单词搜索（某大厂2024面试）

题目描述：
在二维字符矩阵中搜索给定单词是否存在（相邻字母连接）
DFS解法：

bool exist(vector<vector<char>>& board, string word) {
    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[0].size(); ++j) {
            if (dfs(board, word, i, j, 0)) 
                return true;
        }
    }
    return false;
}

bool dfs(vector<vector<char>>& board, string& word, int x, int y, int idx) {
    if (idx == word.size()) return true;
    if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() 
        || board[x][y] != word[idx]) return false;
    
    char tmp = board[x][y];
    board[x][y] = '#'; // 标记已访问
    bool found = dfs(board, word, x+1, y, idx+1)
              || dfs(board, word, x-1, y, idx+1)
              || dfs(board, word, x, y+1, idx+1)
              || dfs(board, word, x, y-1, idx+1);
    board[x][y] = tmp; // 回溯
    return found;
}

真题2：N皇后问题（某大厂2023笔试）

题目描述：
在N×N棋盘放置N个皇后，使其互不攻击
DFS+位运算优化：

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    
    function<void(int, int, int, int)> dfs = [&](int row, int cols, int diag1, int diag2) {
        if (row == n) {
            res.push_back(board);
            return;
        }
        int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
        while (available) {
            int pos = available & -available; // 取最低位的1
            int col = __builtin_ctz(pos); // 计算列索引
            board[row][col] = 'Q';
            dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1);
            board[row][col] = '.';
            available &= available - 1; // 移除最低位的1
        }
    };
    
    dfs(0, 0, 0, 0);
    return res;
}

六、复杂度分析

七、常见误区与调试技巧

1. 栈溢出：递归层数过深（Python默认递归深度约1000层）

   • 解决方案：改用迭代DFS或增大递归限制

2. 状态污染：忘记回溯时恢复共享状态

3. 剪枝错误：错误剪枝导致漏解

4. 调试技巧：

   • 打印递归树路径

   • 使用条件断点跟踪特定路径

   • 可视化中间状态

LeetCode真题训练：

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

• 79. 单词搜索

• 113. 路径总和 II