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

组合

思路：回溯算法

• 问题要求从 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; // 初始化 nk = _k; // 初始化 kdfs(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();   // 回溯：移除最后加入的数字，尝试其他可能性}}
};

目标和

回溯：

• 通过正负号的分配来形成目标和，尝试所有可能的组合。
  如果找到一种方式满足条件，计数+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 开始递归搜索，初始路径和为 0return ret;    // 返回满足条件的方案数}// 深度优先搜索函数，用于枚举所有可能的路径和void dfs(vector<int>& nums, int pos, int path){// 如果已经遍历到数组末尾，检查路径和是否等于目标值if(pos == nums.size()){if(path == aim) ret++; // 如果路径和等于目标值，则方案数加 1return; // 返回，结束当前递归分支}// 选择将当前数字加到路径和dfs(nums, pos + 1, path + nums[pos]);// 选择将当前数字减到路径和dfs(nums, pos + 1, path - nums[pos]);}
};

组合总和

思路：回溯算法

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

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 开始深度优先搜索，当前和为 0return 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();               // 回溯：移除最后一个加入的数字，尝试其他可能性}}
};

字母大小写全排序

思路：回溯算法

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

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;}
};

优美的排列

思路：回溯+剪枝

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

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++;        // 当前排列满足条件，计数加 1return;       // 返回，结束当前递归分支}// 尝试将每个数字放在当前的位置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 的使用状态}}}
};

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; // 取消标记}}}
};