深度优先搜索基础

1.2 DFS的应用场景

• 排列组合问题：
  • 生成全排列
  • 生成所有子集
  • 数字组合问题
• 搜索问题：
  • 数字的所有可能拆分
  • 字符串的所有可能划分
  • 数独求解
• 约束满足问题：
  • N皇后问题
  • 0-1背包问题
  • 硬币找零问题

4.1 DFS模板代码：数组/字符串处理

// 数组子集生成的DFS模板
void subsetDFS(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
    // 处理当前状态（例如：将当前子集加入结果）
    result.push_back(current);
    
    // 遍历所有可能的选择
    for (int i = index; i < nums.size(); i++) {
        // 做选择
        current.push_back(nums[i]);
        
        // 递归处理下一个状态
        subsetDFS(nums, i + 1, current, result);
        
        // 撤销选择（回溯）
        current.pop_back();
    }
    
    // 注意：基本情况（终止条件）通常在递归开始时检查
    // 例如：if (index == nums.size()) return;
}

// 字符串处理的DFS模板
void stringDFS(string& s, int start, vector<string>& current, vector<vector<string>>& result) {
    // 检查基本情况（终止条件）
    if (start >= s.length()) {
        result.push_back(current);
        return;
    }
    
    // 遍历所有可能的选择
    for (int i = start; i < s.length(); i++) {
        // 验证当前选择是否有效
        if (isValid(s, start, i)) {
            // 做选择
            current.push_back(s.substr(start, i - start + 1));
            
            // 递归处理下一个状态
            stringDFS(s, i + 1, current, result);
            
            // 撤销选择（回溯）
            current.pop_back();
        }
    }
}

4.2 DFS模板代码：回溯法

// 回溯法通用模板
void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
    // 判断是否达到终止条件
    if (满足条件) {
        result.push_back(path);
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        // 剪枝：跳过不合法的选择
        if (不合法条件) continue;
        
        // 做选择
        used[i] = true;
        path.push_back(nums[i]);
        
        // 递归进入下一层决策树
        backtrack(nums, used, path, result);
        
        // 撤销选择（回溯）
        path.pop_back();
        used[i] = false;
    }
}

6.1 子集生成

问题描述：给定一个不含重复元素的整数数组，返回该数组所有可能的子集。

思路：使用DFS回溯法，对于每个元素，有"选"和"不选"两种选择。

代码实现：

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    
    // 从索引0开始DFS
    subsetDFS(nums, 0, current, result);
    return result;
}

void subsetDFS(vector<int>& nums, int index, 
               vector<int>& current, vector<vector<int>>& result) {
    // 将当前子集加入结果
    result.push_back(current);
    
    // 从index开始尝试添加每个元素
    for (int i = index; i < nums.size(); i++) {
        // 选择当前元素
        current.push_back(nums[i]);
        // 递归处理剩余元素
        subsetDFS(nums, i + 1, current, result);
        // 回溯，撤销选择
        current.pop_back();
    }
}

6.2 全排列

问题描述：给定一个不含重复数字的数组，返回其所有可能的全排列。

思路：使用回溯法，通过标记已使用的元素，递归生成所有排列。

代码实现：

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    
    backtrack(nums, used, path, result);
    return result;
}

void backtrack(vector<int>& nums, vector<bool>& used, 
               vector<int>& path, vector<vector<int>>& result) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        
        used[i] = true;
        path.push_back(nums[i]);
        
        backtrack(nums, used, path, result);
        
        path.pop_back();
        used[i] = false;
    }
}

6.3 数字组合

问题描述：给定一个正整数数组和目标数，找出所有可能的组合，使得组合中的数字和等于目标数。

思路：使用DFS回溯法，每个数字可以选择或不选择，当和等于目标数时记录组合。

代码实现：

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> current;
    
    combinationDFS(candidates, target, 0, current, result);
    return result;
}

void combinationDFS(vector<int>& candidates, int target, int index,
                   vector<int>& current, vector<vector<int>>& result) {
    // 找到一个合法组合
    if (target == 0) {
        result.push_back(current);
        return;
    }
    
    // 尝试从index开始的每个数字
    for (int i = index; i < candidates.size(); i++) {
        // 剪枝：当前数字太大，跳过
        if (candidates[i] > target) continue;
        
        // 选择当前数字
        current.push_back(candidates[i]);
        // 递归处理剩余目标值
        combinationDFS(candidates, target - candidates[i], i, current, result);
        // 回溯，撤销选择
        current.pop_back();
    }
}

6.4 字符串分割

问题描述：给定一个字符串，将其分割成若干子串，使得每个子串都是回文串。返回所有可能的分割方案。

思路：使用DFS回溯法，在每个位置尝试分割，判断分割出的子串是否为回文串。

代码实现：

vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    vector<string> current;
    
    partitionDFS(s, 0, current, result);
    return result;
}

void partitionDFS(string& s, int start, 
                  vector<string>& current, vector<vector<string>>& result) {
    // 已处理完整个字符串，记录结果
    if (start >= s.length()) {
        result.push_back(current);
        return;
    }
    
    // 尝试从start开始的每个可能的分割点
    for (int i = start; i < s.length(); i++) {
        // 判断子串是否为回文
        if (isPalindrome(s, start, i)) {
            // 选择当前分割方案
            current.push_back(s.substr(start, i - start + 1));
            // 递归处理剩余子串
            partitionDFS(s, i + 1, current, result);
            // 回溯，撤销选择
            current.pop_back();
        }
    }
}

bool isPalindrome(string& s, int start, int end) {
    while (start < end) {
        if (s[start++] != s[end--]) return false;
    }
    return true;
}

7. 总结

• DFS是一种重要的搜索算法，适用于各种图遍历和状态空间搜索问题
• 掌握DFS的核心思想：深度优先、回溯、状态转移
• 理解不同类型的DFS应用：图遍历、状态空间搜索、回溯法
• 熟练运用剪枝和优化技巧，提高搜索效率
• DFS与其他算法（如BFS、动态规划）结合，可以解决更复杂的问题