【递归与回溯深度解析：经典题解精讲（中篇）】—

文章目录

组合
目标和
组合总和
字母大小写全排序
优美的排列
N皇后

leetcode.cn/problems/combinations/description/" rel="nofollow">组合

在这里插入图片描述
思路：回溯算法

问题要求从 1 到 n 中选出 k 个数的所有组合。
使用回溯算法递归构造解。
每次递归时，记录当前的组合路径，当组合长度达到 k 时，将其加入结果集。
剪枝优化：在递归过程中，如果当前选择的起点到 n 不够 k 个数，就停止递归。

class Solution 
{
    vector<vector<int>> ret; // 用于存储最终的所有组合结果
    vector<int> path;        // 用于存储当前正在构建的组合
    int n, k;                // n 表示范围 [1, n]，k 表示组合的大小

public:
    vector<vector<int>> combine(int _n, int _k) 
    {
        n = _n; // 初始化 n
        k = _k; // 初始化 k
        dfs(1); // 从数字 1 开始进行深度优先搜索
        return ret; // 返回所有的组合结果
    }

    // 深度优先搜索函数，用于生成所有的组合
    void dfs(int pos)
    {
        // 如果当前组合的大小等于 k，则将该组合加入结果集
        if(k == path.size())
        {
            ret.push_back(path); // 将当前组合存储到结果集中
            return; // 返回，结束当前递归分支
        }

        // 从当前数字 pos 开始，尝试加入到组合中
        for(int i = pos; i <= n; i++)
        {
            path.push_back(i); // 将当前数字加入到组合中
            dfs(i + 1);        // 递归调用，处理下一个数字，确保数字不会重复
            path.pop_back();   // 回溯：移除最后加入的数字，尝试其他可能性
        }
    }
};

leetcode.cn/problems/target-sum/description/" rel="nofollow">目标和

在这里插入图片描述
回溯：

通过正负号的分配来形成目标和，尝试所有可能的组合。
如果找到一种方式满足条件，计数+1。

class Solution 
{
    int ret, aim; // `ret` 用于存储满足条件的方案总数，`aim` 是目标值

public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        aim = target; // 初始化目标值
        ret = 0;      // 初始化方案数
        dfs(nums, 0, 0); // 从索引 0 开始递归搜索，初始路径和为 0
        return ret;    // 返回满足条件的方案数
    }

    // 深度优先搜索函数，用于枚举所有可能的路径和
    void dfs(vector<int>& nums, int pos, int path)
    {
        // 如果已经遍历到数组末尾，检查路径和是否等于目标值
        if(pos == nums.size())
        {
            if(path == aim) ret++; // 如果路径和等于目标值，则方案数加 1
            return; // 返回，结束当前递归分支
        }

        // 选择将当前数字加到路径和
        dfs(nums, pos + 1, path + nums[pos]);

        // 选择将当前数字减到路径和
        dfs(nums, pos + 1, path - nums[pos]);
    }
};

leetcode.cn/problems/combination-sum/description/" rel="nofollow">组合总和

在这里插入图片描述
思路：回溯算法

使用回溯方法，试图从给定的数字中选出若干个数（可重复）使其和为目标值。
在递归过程中：
当前路径的总和如果大于目标值，停止搜索。
如果总和等于目标值，将当前路径加入结果。
每次递归时从当前数字开始，避免重复路径。

class Solution 
{
    int aim;                     // 目标和
    vector<vector<int>> ret;     // 存储所有满足条件的组合
    vector<int> path;            // 存储当前路径（正在构建的组合）

public:
    vector<vector<int>> combinationSum(vector<int>& nums, int target) 
    {
        aim = target;            // 设置目标和
        dfs(nums, 0, 0);         // 从索引 0 开始深度优先搜索，当前和为 0
        return ret;              // 返回所有符合条件的组合
    }

    // 深度优先搜索函数
    void dfs(vector<int>& nums, int pos, int sum)
    {
        // 如果当前和等于目标值，将当前组合加入结果集
        if(sum == aim)
        {
            ret.push_back(path); // 将当前路径（组合）存入结果集
            return;              // 返回，结束当前递归分支
        }
        
        // 如果当前和超过目标值，或索引超出数组范围，则返回
        if(sum > aim || pos == nums.size()) return;

        // 从当前索引 `pos` 开始，尝试每个数字
        for(int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);        // 将当前数字加入到路径中
            dfs(nums, i, sum + nums[i]);   // 递归调用，允许重复选择当前数字
            path.pop_back();               // 回溯：移除最后一个加入的数字，尝试其他可能性
        }
    }
};

leetcode.cn/problems/letter-case-permutation/" rel="nofollow">字母大小写全排序

在这里插入图片描述
思路：回溯算法

遍历字符串，每遇到一个字母字符，就有两种选择（小写或大写）。
使用递归构造所有可能的字符串路径：
对于每个字符，选择原字符或大小写转换后的字符加入路径。
遇到数字时，直接加入路径。
当遍历到字符串末尾时，将路径加入结果集。

class Solution 
{
    vector<string> ret; // 用于存储所有满足条件的字符串组合
    string path;        // 当前正在构建的路径（部分字符串）

public:
    vector<string> letterCasePermutation(string s) 
    {
        dfs(s, 0); // 从字符串的第 0 个字符开始深度优先搜索
        return ret; // 返回所有可能的组合结果
    }

    // 深度优先搜索函数
    void dfs(string& s, int pos)
    {
        // 如果当前处理位置等于字符串长度，说明路径构造完成
        if(pos == s.size())
        {
            ret.push_back(path); // 将路径加入结果集
            return;              // 返回，结束当前递归分支
        }

        char ch = s[pos];
        // 情况 1：不改变当前字符，直接加入路径
        path.push_back(ch);
        dfs(s, pos + 1); // 递归处理下一个字符
        path.pop_back(); // 回溯，移除当前字符

        // 情况 2：改变当前字符的大小写
        if(ch < '0' || ch > '9') // 如果当前字符不是数字，尝试改变大小写
        {
            char tmp = change(ch); // 改变字符大小写
            path.push_back(tmp);   // 将改变后的字符加入路径
            dfs(s, pos + 1);       // 递归处理下一个字符
            path.pop_back();       // 回溯，移除改变后的字符
        }
    }

    // 辅助函数：改变字符的大小写
    char change(char ch)
    {
        if(ch <= 'z' && ch >= 'a') ch -= 32; // 小写转大写
        else ch += 32;                       // 大写转小写
        return ch;
    }
};

leetcode.cn/problems/beautiful-arrangement/description/" rel="nofollow">优美的排列

在这里插入图片描述
思路：回溯+剪枝

使用回溯法，尝试将数字放入数组中。
每次递归时，判断当前数字是否满足条件（能被当前位置整除或能整除当前位置）。
剪枝优化：如果当前排列不符合条件，提前停止递归。

class Solution 
{
    int ret;              // 用于记录满足条件的排列方案数
    bool check[16];       // 用于记录数字是否被使用过（数组下标从 1 开始）

public:
    int countArrangement(int n) 
    {
        dfs(n, 1);        // 从位置 1 开始深度优先搜索
        return ret;       // 返回最终的方案数
    }

    // 深度优先搜索函数
    void dfs(int n, int pos)
    {
        // 递归终止条件：如果当前位置超出 n，说明排列完成
        if(pos == n + 1)
        {
            ret++;        // 当前排列满足条件，计数加 1
            return;       // 返回，结束当前递归分支
        }

        // 尝试将每个数字放在当前的位置
        for(int i = 1; i <= n; i++)
        {
            // 如果数字 i 尚未被使用，且满足题目中的条件
            if(!check[i] && (pos % i == 0 || i % pos == 0))
            {
                check[i] = true;    // 标记数字 i 已被使用
                dfs(n, pos + 1);    // 递归处理下一个位置
                check[i] = false;   // 回溯：取消数字 i 的使用状态
            }
        }
    }
};

leetcode.cn/problems/n-queens/description/" rel="nofollow">N皇后

在这里插入图片描述
思路：回溯+剪枝

使用回溯法尝试将 N 个皇后放置到 N×N 棋盘上。
在递归过程中，每一行尝试放置一个皇后：
检查当前列、主对角线、副对角线是否已被占用。
剪枝优化：利用标志数组记录列、主对角线、副对角线是否被占用，避免重复检查。
当所有行都放置完成时，将当前结果加入结果集。

class Solution 
{
    bool checkCol[10], checkdig1[20], checkdig2[20]; // 分别记录列、主对角线、副对角线是否被占用
    vector<vector<string>> ret; // 存储所有符合条件的棋盘配置
    vector<string> path;        // 当前棋盘状态
    int n;                      // 棋盘的大小

public:
    vector<vector<string>> solveNQueens(int _n) 
    {
        n = _n;                  // 初始化棋盘大小
        path.resize(n);          // 初始化棋盘状态
        for(int i = 0; i < n; i++)
            path[i].append(n, '.'); // 将每一行初始化为 `n` 个 '.'（表示空位置）
        dfs(0);                  // 从第 0 行开始深度优先搜索
        return ret;              // 返回所有符合条件的棋盘配置
    }

    // 深度优先搜索函数
    void dfs(int row)
    {
        // 递归终止条件：如果已经处理到第 n 行，说明所有皇后都已放置完成
        if(row == n)
        {
            ret.push_back(path); // 将当前棋盘状态加入结果集
            return;              // 返回，结束当前递归分支
        }

        // 遍历当前行的每一列，尝试放置皇后
        for(int col = 0; col < n; col++)
        {
            // 检查当前列、主对角线、副对角线是否被占用
            if(!checkCol[col] && !checkdig1[row - col + n] && !checkdig2[row + col])
            {
                // 放置皇后，更新棋盘状态和限制条件
                path[row][col] = 'Q';                             // 在 (row, col) 放置皇后
                checkCol[col] = checkdig1[row - col + n] = checkdig2[row + col] = true; // 标记当前位置

                dfs(row + 1); // 递归处理下一行

                // 回溯：移除皇后，恢复棋盘状态和限制条件
                path[row][col] = '.';                             // 移除 (row, col) 的皇后
                checkCol[col] = checkdig1[row - col + n] = checkdig2[row + col] = false; // 取消标记
            }
        }
    }
};