暴搜、深搜、回溯算法题集

本文主要是介绍暴搜、深搜、回溯算法题集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 全排列

step1：画出决策树：越详细越好
step2：设计代码
全局变量的设计：

vector<vector<int>> ret; // 用于存储结果
vector<int> path; // 用于存储遍历过程中经过的路径
vector<bool> check; // 对已经选择了的数进行标记，根据标记了的数进行剪枝

DFS函数的设计：
仅需关心某一个节点在干什么事情即可。
细节问题：

• 回溯：回溯就是一层递归结束之后，变量的状态要复原，对于path则要pop掉最后一个元素；对于check数组则要修改并复原。
• 递归出口：遇到叶子结点，将结果插入

参考答案：

class Solution {
public:vector<vector<int>> ret;vector<int> path;vector<bool> check;void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(check[i] == false) {path.push_back(nums[i]);check[i] = true;} else continue; // check[i] == true则要剪枝dfs(nums);path.pop_back(); // 回溯: 恢复现场check[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {check.resize(nums.size());dfs(nums);return ret;}
};

2. 全排列II

这题和上一题的不同点：除了在dfs时需要对选过的元素进行剪枝外，当回溯的时候应将重复的元素进行剪枝，避免后序dfs时会出现重复的排列。

写法一：只关心“不合法”的分支

class Solution {
public:vector<int> path;vector<vector<int>> ret;vector<bool> check; // check数组用于确保选到的数字不是同一个位置的数void dfs(const vector<int>& nums) {if (path.size() == nums.size()) {ret.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (check[i] == true || (i > 0 && check[i-1] == false && nums[i-1] == nums[i])) {continue;}path.push_back(nums[i]);check[i] = true;dfs(nums);path.pop_back();check[i] = false;}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());check.resize(nums.size());dfs(nums);return ret;}
};

写法二：只关心“合法”的分支

class Solution {
public:vector<int> path;vector<vector<int>> ret;vector<bool> check; // check数组用于确保选到的数字不是同一个位置的数void dfs(const vector<int>& nums) {if (path.size() == nums.size()) {ret.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (check[i] == false && (i == 0 || check[i-1] == true || nums[i-1] != nums[i])){path.push_back(nums[i]);check[i] = true;dfs(nums);path.pop_back();check[i] = false;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());check.resize(nums.size());dfs(nums);return ret;}
};

3. 子集

解法一：

class Solution {
public:vector<vector<int>> ret;vector<int> path;void dfs(const vector<int>& nums, int startindex){if(startindex == nums.size()){ret.push_back(path);return;}// 不选, 直接进入下一层递归dfs(nums, startindex + 1);// 选path.push_back(nums[startindex]);dfs(nums, startindex + 1);path.pop_back(); // 恢复之前递归的状态}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}
};

解法二：

dfs每一轮遍历的节点组成的集合都是结果集，显然要比方法一高效。

class Solution {
public:vector<int> path;vector<vector<int>> ret;void dfs(const vector<int>& nums, int pos){ret.push_back(path);for(int i = pos; i < nums.size(); i++){path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back();}return;}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}
};

4. 子集II

5. 找出所有子集的异或总和再求和

这题是基于集合那一题的，对求得的集合里面的元素进行异或。

写法一：

class Solution {
public:vector<int> path;vector<vector<int>> ret;void dfs(const vector<int>& nums, int pos) {ret.push_back(path);for (int i = pos; i < nums.size(); i++) {path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back();}return;}int subsetXORSum(vector<int>& nums) {dfs(nums, 0);int sum = 0;for (auto& ch1 : ret) {int prev = 0;for (auto& ch2 : ch1) {prev ^= ch2;}sum += prev;}return sum;}
};

实际上我们无需一整个数组保存所有的节点，我们只需要求得子集中最终异或的结果即可，那么我们只需要用一个变量保存这个结果即可。
写法二：

class Solution {
public:int path;int sum;void dfs(const vector<int>& nums, int pos) {sum += path;for (int i = pos; i < nums.size(); i++) {path ^= nums[i];dfs(nums, i + 1);path ^= nums[i]; // 回溯: 恢复现场}return;}int subsetXORSum(vector<int>& nums) {dfs(nums, 0);return sum;}
};

6. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

提示：

    0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。

画出决策图很重要，接下来就是照着决策图写代码了。

class Solution {
public:string telnum[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> ret;string path;void dfs(const string& digits, int pos){if(pos == digits.size()){ret.push_back(path);return;}int char2num = digits[pos] - '0';string letter = telnum[char2num];for(int i = 0; i < letter.size(); i++){path += letter[i];dfs(digits, pos + 1);path.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size() == 0) return ret;dfs(digits, 0);return ret;}
};

7. 括号生成

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：

输入：n = 1
输出：[“()”]

提示：

    1 <= n <= 8

如何保证组合是有效的括号？要满足下面的条件。

1. 整个字符串中，左括号的数量 = 右括号的数量
2. 从头开始的任意一个子串，左括号的数量 >= 右括号的数量

剪枝条件：
记左括号的数目为left，右括号的数目为right，左括号或右括号的总数为n。
当left >= n时，左括号的数目(==时为即将)超过了上限，要剪枝；right >= left时，右括号的数目(即将)超过了左括号，要剪枝

class Solution {
public:vector<string> ret;string path;int left, right, n;void dfs(){if(right == n){ret.push_back(path);return;}// 先插入左括号(if(left < n){left++;path.push_back('(');dfs();left--;path.pop_back();}// 再插入右括号)if(left > right){right++;path.push_back(')');dfs();right--;path.pop_back();} }vector<string> generateParenthesis(int _n) {n = _n;dfs();return ret;}
};

8. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例 1:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2:

输入: n = 1, k = 1
输出: [[1]]

提示:

    1 <= n <= 201 <= k <= n

这道题给的数据是连续的数字，我们不用担心会出现重复的数字而去创建一个check数组去考虑去重的操作。

class Solution {
public:vector<vector<int>> ret;vector<int> path;void dfs(int n, int k, int startindex){if(path.size() == k){ret.push_back(path);return;}for(int i = startindex; i <= n; i++){path.push_back(i);dfs(n, k, i + 1); // 每次dfs要从下一个位置开始递归, 不能往回走, 避免重复的组合以及避免选到重复元素path.pop_back();}return;}vector<vector<int>> combine(int n, int k) {dfs(n, k, 1);return ret;}
};

9. 目标和

写法一：path作为全局变量

class Solution {
public:int ret = 0, path = 0;int target;void dfs(vector<int>& nums, int pos){if(pos >= nums.size()){if(path == target) ret++;return;}// 先处理'+'path += nums[pos];dfs(nums, pos + 1);path -= nums[pos]; // 恢复现场// 再处理'-'path -= nums[pos];dfs(nums, pos + 1);path += nums[pos]; // 恢复现场return;}int findTargetSumWays(vector<int>& nums, int _target) {target = _target;dfs(nums, 0);return ret;}
};

写法二：path作为形参

class Solution {
public:int ret = 0;int target;void dfs(vector<int>& nums, int path, int pos){if(pos >= nums.size()){if(path == target) ret++;return;}// 先处理'+'dfs(nums, path + nums[pos], pos + 1);// 再处理'-'dfs(nums, path - nums[pos], pos + 1);return;}int findTargetSumWays(vector<int>& nums, int _target) {target = _target;dfs(nums, 0, 0);return ret;}
};

10. 组合总和

解法一：每一层选择数组的元素

class Solution {
public:vector<vector<int>> ret;vector<int> path;int target;void dfs(vector<int>& candidates, int sum, int pos){if(sum == target){ret.push_back(path);return;}for(int i = pos; i < candidates.size(); i++){if(sum < target) // 对于大于target的部分要剪枝{path.push_back(candidates[i]);dfs(candidates, sum + candidates[i], i); // 注意这里的pos应该是i, i前面的元素会造成重复集合, 应剪枝!!!path.pop_back(); // 回溯}}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates, 0, 0);return ret;}
};

解法二：每一层选择一个元素的个数

class Solution {
public:vector<vector<int>> ret;vector<int> path;int target;void dfs(vector<int>& candidates, int sum, int pos){if(sum == target){ret.push_back(path);return;}if(sum > target || pos == candidates.size()) return;// 枚举个数for(int k = 0; sum + k*candidates[pos] <= target; k++){if(k) path.push_back(candidates[pos]);dfs(candidates, sum + k*candidates[pos], pos + 1);}// 回溯, 恢复现场for(int k = 1; sum + k*candidates[pos] <= target; k++){path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates, 0, 0);return ret;}
};

11. 组合总和II

与组合总和I的不同点：1，组合总和I允许一个元素选多次，组合总和II中每一个元素只能选一次；2，组合总和I的整数数组中无重复元素，而组合总和II中整数数组中有重复元素，因此要对重复的元素进行剪枝。

class Solution {
public:vector<vector<int>> ret;vector<int> path;vector<bool> check;int aim;void dfs(vector<int>& candidates, int sum, int pos){if(sum == aim){ret.push_back(path);return;}if(sum > aim) return;for(int i = pos; i < candidates.size(); i++){// 组合总和II的集合中有重复元素, 要对重复元素进行剪枝去重if(i > 0 && candidates[i-1] == candidates[i] && check[i-1] == false) continue; path.push_back(candidates[i]);check[i] = true;// 这里是i + 1, 因为这题和组合总和I不一样, 这里不能重复选取元素dfs(candidates, sum + candidates[i], i + 1); path.pop_back();check[i] = false;}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {aim = target;check.resize(candidates.size());sort(candidates.begin(), candidates.end());dfs(candidates, 0, 0);return ret;}
};

12. 组合总和III

这题要注意的是，从1到9选k个数，并且总和为n，第一要控制个数，第二要控制总和。

class Solution {
public:vector<vector<int>> ret;vector<int> path;int aim;void dfs(int k, int sum, int pos){if(sum == aim && path.size() == k){ret.push_back(path);return;}if(sum > aim || path.size() > k) return;for(int i = pos; i <= 9; i++){path.push_back(i);dfs(k, sum + i, i + 1);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {aim = n;dfs(k, 0, 1);return ret;}
};

13. 字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1：

输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

示例 2:

输入: s = “3z4”
输出: [“3z4”,“3Z4”]

提示:

    1 <= s.length <= 12s 由小写英文字母、大写英文字母和数字组成

class Solution {
public:vector<string> ret;string path;void dfs(string& s, int pos){if(pos == s.size()) {ret.push_back(path);return;}if(s[pos] >= '0' && s[pos] <= '9') // 数字{path += s[pos];dfs(s, pos + 1);path.pop_back();}else // 字母{char alpha = s[pos];if(alpha < 'a' || alpha > 'z')alpha -= ('A' - 'a'); // 如果是大写就转换成小写// 先选小写path += alpha;dfs(s, pos + 1);path.pop_back();// 再选大写path += alpha + ('A' - 'a');dfs(s, pos + 1);path.pop_back();}}vector<string> letterCasePermutation(string s) {dfs(s, 0);return ret;}
};

14. 优美的排列

class Solution {
public:int ret;vector<bool> check;void dfs(int index, int n){if(index == n + 1){ret++;return;}for(int i = 1; i <= n; i++){if(check[i] == false && (i % index == 0 || index % i == 0)){check[i] = true;dfs(index + 1, n);check[i] = false;}}}int countArrangement(int n) {check.resize(n + 1);dfs(1, n); // 从1开始枚举, 填n个数return ret;}
};

15. N 皇后

算法原理：
从棋盘的每一行开始考虑，for循环负责遍历棋盘的行的每一个格子，将皇后放在格子上；深度优先遍历负责遍历下一行

剪枝策略：
为确保皇后的同一行，同一列和同一斜线方向上的旗子不会相互攻击，那么就要对上述的决策树进行判断，将符合不被攻击的情况筛选出来。
策略一：
最暴力的解法是，每遍历到一个棋盘，就对这个皇后的同一行，同一列和同一斜线方向上进行遍历，如果遇到了别的旗子，那么就会受到攻击，这种情况不需要记录，直接进行下一趟遍历，那么整个dfs(O(2^N))及寻找是否会受到攻击(O(4N))的时间复杂度是：O(4N * 2^N)。
策略二：
用哈希表记录每个旗子的下标，当我遍历到对应的位置时，能通过当前的下标判断是否和之前的旗子有互相攻击的关系。
（一）当两个旗子横坐标相同时会相互攻击，行方向的哈希表用布尔数组表示，横坐标对应的哈希值为true代表会相互攻击，横坐标对应的哈希值为false代表会相互攻击。布尔数组表示为bool row[n];
（二）当两个旗子纵坐标相同时会相互攻击。布尔数组表示为bool col[n];
（三）斜方向上，我们用截距当作哈希数组的key值，不同旗子的下标算出来的截距如果相同的话，那么就会相互攻击。
情况一：斜率为1
布尔数组表示为bool dig1[2*n];// 表示主对角线
情况二：斜率为-1
布尔数组表示为bool dig2[2*n];// 表示副对角线

class Solution {
public:vector<vector<string>> ret;vector<string> path;vector<bool> checkCol; // 这里无需创建一个checkrow了，因为水平方向我每次添加了元素后还会回溯恢复现场，也就是说我能控制一行只添加一个元素，无需判断vector<bool> checkdig1;vector<bool> checkdig2;void dfs(int n, int row){if(row == n){ret.push_back(path);return;}for(int col = 0; col < n; col++) // 在这一行放皇后{// 剪枝if(checkCol[col] == true || checkdig1[col - row + n] == true || checkdig2[col + row] == true) continue;path[row][col] = 'Q';checkCol[col] = checkdig1[col - row + n] = checkdig2[col + row] = true;dfs(n, row + 1);// 恢复现场path[row][col] = '.';checkCol[col] = checkdig1[col - row + n] = checkdig2[col + row] = false;}return;}vector<vector<string>> solveNQueens(int n) {path.resize(n);for(auto& a : path) a.append(n, '.');checkCol.resize(n);checkdig1.resize(2*n);checkdig2.resize(2*n);dfs(n, 0);return ret;}
};

16. 有效的数独

如何验证已经填入的数字是否有效？
算法原理：
用hash数组去标记当前行有无重复元素，当前列有无重复元素，9宫格有无重复元素。
（1）当前行有无重复元素
用bool row[9][10]表示，下标含义是：如row[2][3]表示，第2行的元素3是否存在，存在为true，不存在为false。
（2）当前列有无重复元素
用bool col[9][10]表示，下标含义是：如col[8][3]表示，第8列的元素3是否存在，存在为true，不存在为false。
（3）9宫格有无重复元素

class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {if(board[i][j] != '.'){int num = board[i][j] - '0';// 判断是否是有效的if(row[i][num] == true || col[j][num] == true || grid[i/3][j/3][num] == true)return false;// 遍历过的数字在hash中的位置标记为truerow[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}return true;}
};

17. 解数独

算法原理：

class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];bool dfs(vector<vector<char>>& board){// 暴力枚举board的每一个格子for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {if(board[i][j] == '.'){// 在空格的位置填入1~9，依次试一遍for(char k = '1'; k <= '9'; k++){// 判断num是否合法, 不合法就找下一个int num = k - '0';if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num]){// num暂时合法, 先填到board中, 进入下一层递归board[i][j] = k;row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;if(dfs(board) == true) return true; // 当前层填的没问题, 向上返回trueboard[i][j] = '.'; // 回溯的时候return false表现在我要恢复原来的状态, 现在的结果不合法row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}// 能走到这里说明for循环里没有return truereturn false;}}}return true;}void solveSudoku(vector<vector<char>>& board) {// 先把board里面存在的数标记一下for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {if(board[i][j] != '.') {int num = board[i][j] - '0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}dfs(board);}
};

18. 单词搜索

算法原理：

如何取遍历一个节点的上下左右呢？
向量偏移法：
具体使用见代码实现。

class Solution {
public:int dx[4] = {-1, 1, 0, 0}; // 上下左右的下标x的变化int dy[4] = {0, 0, -1, 1}; // 上下左右的下标x的变化int m, n;bool visit[100][100];bool dfs(vector<vector<char>>& board, string word, int x, int y, int pos){if(pos == word.size()) return true; // 单词匹配完了还没有出错就返回true// 第一个位置找到了, dfs坐标(x,y)的上下左右四个方向, 看有没有符合要求的for(int k = 0; k < 4; k++){int i = x + dx[k], j = y + dy[k];if(    i >= 0 && i < m              // i不能越界&& j >= 0 && j < n              // j不能越界&& visit[i][j] == false         // (i,j)未被使用过&& board[i][j] == word[pos])    // (i,j)位置的值和word[pos]要能匹配{visit[i][j] = true;if(dfs(board, word, i, j, pos + 1)) return true;visit[i][j] = false;}}// 四个方向都没找到就回溯, 去找另一个位置return false;}bool exist(vector<vector<char>>& board, string word) {m = board.size(), n = board[0].size();// 先找单词的第一个字母for(int i = 0; i < board.size(); i++) {for(int j = 0; j < board[0].size(); j++) {if(board[i][j] == word[0] && visit[i][j] == false){visit[i][j] = true;if(dfs(board, word, i, j, 1)) return true;visit[i][j] = false;}}}return false;}
};

19. 黄金矿工

算法原理：

class Solution {
public:int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};bool vis[16][16];int ret, m, n;void dfs(vector<vector<int>>& grid, int i, int j, int path){// 递归出口: 可以不用写, 这题递归出口要写很多判断很麻烦// 其实递归出口就隐藏在了下面的for循环中, 当遇到0时就不会进入dfs// 每进入一次递归就更新一次结果, 这样能保证不遗漏ret = path > ret ? path : ret;for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m&& y >= 0 && y < n&& grid[x][y] != 0&& vis[x][y] == false){vis[x][y] = true;dfs(grid, x, y, path + grid[x][y]);vis[x][y] = false;}}}int getMaximumGold(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {// 找到第一个不是空的单元格if(grid[i][j] != 0){vis[i][j] = true;dfs(grid, i, j, grid[i][j]);vis[i][j] = false;}}}return ret;}
};

20. 不同路径III

算法原理：
这题别看他是困难题，其实思路和前面两题是一样的，都是运用暴搜的思路，将所有的路径搜索出来，还需要对合法路径进行判断。
合法路径如何判断？
合法路径指的是从1到2，要经过所有的非障碍物的路径。我们可以用一个count记录每次走过的步数，用step表示从1到2的合法路径的步数，比较count和step即可判断是否合法。

class Solution {
public:int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};bool vis[20][20];int m, n;int ret = 0, count = 0, step = 2;void dfs(vector<vector<int>>& grid, int i, int j) {// 走到重点if(grid[i][j] == 2){if(count == step) ret++; // 判断路径是否合法return;}// 上下左右去dfsfor(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m&& y >= 0 && y < n&& grid[x][y] != -1&& vis[x][y] == false){vis[x][y] = true;count++;dfs(grid, x, y);vis[x][y] = false;count--;}}}int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();// 1. 统计一共要走多少步, 0的个数 + 2(1和2)// 2. 标记1的位置int starti = 0, startj = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j] == 0)step++;else if(grid[i][j] == 1) starti = i, startj = j;vis[starti][startj] = true;count++;dfs(grid, starti, startj);return ret;}
};

这篇关于暴搜、深搜、回溯算法题集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---