文章目录
- 回溯
- 电话号码的字母组合
- 二进制手表
- 组合总数
- 全排列
- 活字印刷
- N皇后
- N皇后II
回溯
回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。
当探索到某一步时，发现原先选择并不优或 达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。也可以称为剪枝点，所谓的剪枝，指的是把不会找到目标，或者不必要的路径裁剪掉。
从上面看出，回溯其实就是选优搜索法，按照深度优先搜索的方式进行搜索，再通过剪枝来避免不相关结果。
//模板
回溯()
{
if(满足结束条件)
{
将结果加入结果集中
return;
}
for(当前选择 : 选择列表)
{
1.完成这一步的选择
2.回溯(下一步), 进行下一步的选择
3.撤销选择，继续进行其他尝试
}
}
电话号码的字母组合
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
DFS + 回溯，如果当前组合行不通则回溯到上一步，然后继续尝试其他组合。
class Solution {
public:
vector<string> numToStr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; //数字——字母映射
void DFS(vector<string>& res, string& digits, string cur, int index)
{
//此时数字已遍历结束
if(index == digits.size())
{
//如果组合不为空，则加入结果集中
if(!cur.empty())
{
res.push_back(cur);
return;
}
}
//搜索当前所有可能的组合
for(auto ch : numToStr[digits[index] - '0'])
{
cur.push_back(ch);
DFS(res, digits, cur, index + 1);
//回溯到上一步的状态
cur.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.empty())
{
return {};
}
vector<string> res;
DFS(res, digits, "", 0);
return res;
}
};
二进制手表
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。
例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-watch
和上题思路一样，不过变为了组合二进制。
class Solution {
public:
vector<int> nToTime = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};
void DFS(vector<string>& res, int num, int index, pair<int, int>& time)
{
//如果没有剩余的灯，就返回
if(num == 0)
{
if(time.first > 11 || time.second > 59)
{
return;
}
string cur = (to_string(time.first) + ":");
if(time.second < 10) //小于10要补0
{
cur += '0';
}
cur += to_string(time.second);
res.push_back(cur); //组合结果
return;
}
//尝试当前每一种组合
for(int i = index; i < 10; i++)
{
//超出范围,舍弃该数据
if(time.first > 11 || time.second > 59)
{
continue;
}
pair<int, int> backUp = time;
//前四个灯为小时
if(i < 4)
{
time.first += nToTime[i];
}
//后六个灯为分钟
else
{
time.second += nToTime[i];
}
DFS(res, num - 1, i + 1, time); //进入下一层搜索, 下次从第i + 1栈灯开始
time = backUp; //回溯状态
}
}
vector<string> readBinaryWatch(int num) {
vector<string> res;
pair<int, int> time(0, 0);
DFS(res, num, 0, time);
return res;
}
};
组合总数
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
和上面的思路一样，不过此时由于数据可以无限被选取，所以搜索时下一步的位置还是从当前位置i开始，不需要继续推进。(这道题目也可以当成完全背包，与动态规划题解中的零钱问题II类似)
class Solution {
public:
void DFS(vector<int>& candidates, vector<vector<int>>& res, vector<int>& cur, int target, int sum, int index)
{
//如果大于等于target，则不可再增加
if(sum >= target)
{
//如果和target相等则返回结果集
if(sum == target)
{
res.push_back(cur);
}
return;
}
//尝试当前各种结果
for(int i = index; i < candidates.size(); i++)
{
//如果当前元素比target大,则不可能成立，直接跳过
if(candidates[i] > target)
{
continue;
}
cur.push_back(candidates[i]);
DFS(candidates, res, cur, target, sum + candidates[i], i); //由于此时数据可以被无限选取，所以下一步的位置继续从i开始搜索
cur.pop_back(); //回溯
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if(candidates.empty())
{
return {};
}
vector<vector<int>> res;
vector<int> cur;
DFS(candidates, res, cur, target, 0, 0);
return res;
}
};
全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
照着模板就可以写出来
class Solution {
public:
void DFS(vector<vector<int>>& allRet, vector<int>& curRet, vector<int>& nums, vector<bool>& visited)
{
//满足条件则加入结果集
if(curRet.size() == nums.size())
{
allRet.push_back(curRet);
}
for(int i = 0; i < nums.size(); i++)
{
//跳过以访问数字
if(visited[i] == false)
{
continue;
}
//记录当前结果
curRet.push_back(nums[i]);
visited[i] = false;
//进行下一步的搜索
DFS(allRet, curRet, nums, visited);
//回溯
curRet.pop_back();
visited[i] = true;
}
}
vector<vector<int>> permute(vector<int>& nums) {
if(nums.empty())
{
return {};
}
vector<vector<int>> allRet;
vector<int> curRet;
vector<bool> visited(nums.size(), true);
DFS(allRet, curRet, nums, visited);
return allRet;
}
};
活字印刷
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-tile-possibilities
全排列的变形，此时变为处理字符串，并且返回任意可以印出的组合
1.当前组合不为空, 则插入set中
2.继续给当前组合拼接新的组合，尝试拼接tiles每一个位置的字符
3.如果当前位置已在组合中出现过，跳过该位置，否则标记当前位置，继续拼接更长的组合
4.回溯，尝试组合其它位置，返回
class Solution {
public:
void DFS(unordered_set<string>& set, vector<bool>& visited, string& tiles, string cur)
{
//结果不为空则记录下来
if(!cur.empty())
{
set.insert(cur);
}
for(int i = 0; i < tiles.size(); i++)
{
//如果当前字模已经用过, 则跳过本轮
if(visited[i] == false)
{
continue;
}
//记录当前位
cur.push_back(tiles[i]);
visited[i] = false;
//查找下一位
DFS(set, visited, tiles, cur);
//回溯, 继续尝试其他组合
visited[i] = true;
cur.pop_back();
}
}
int numTilePossibilities(string tiles) {
if(tiles.empty())
{
return 0;
}
unordered_set<string> set; //结果集, 去重
vector<bool> visited(tiles.size(), true); //标记矩阵
DFS(set, visited, tiles, "");
return set.size();
}
};
N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
具体思路看注释，主要就是尝试所有排列组合，并判断行，列，左右对角线是否存在其他皇后，然后将所有符合条件的结果保存下来即可。
class Solution {
public:
void DFS(vector<vector<pair<int, int>>>& allRes, vector<pair<int, int>>& curRes, int curRow, int n)
{
//此时说明已经走完, 记录结果
if(curRow == n)
{
allRes.push_back(curRes);
}
for(int i = 0; i < n; i++)
{
//如果当前符合规则, 则继续, 如果不符合直接忽略
if(isVaild(curRes, curRow, i))
{
//记录当前行位置
curRes.push_back(make_pair(curRow, i));
//查找下一行
DFS(allRes, curRes, curRow + 1, n);
//回溯
curRes.pop_back();
}
}
}
bool isVaild(vector<pair<int, int>>& curRes, int row, int col)
{
//判断当前位置是否合法, 各皇后不能放在同一条直线上
for(const pair<int, int>& cur : curRes)
{
if(cur.first == row //判断当前行
|| cur.second == col //判断当前列
|| cur.first + cur.second == row + col //判断左对角线
|| cur.first - cur.second == row - col) //判断右对角线
{
return false;
}
}
return true;
}
//将坐标结果转换为字符串的棋盘
vector<vector<string>> resToString(vector<vector<pair<int, int>>>& allRes, int n)
{
vector<vector<string>> res;
for(const vector<pair<int, int>>& cur : allRes)
{
vector<string> curRes(n, string(n, '.')); //初始化棋盘
for(const pair<int, int>& pos : cur) //将皇后放入棋盘中
{
curRes[pos.first][pos.second] = 'Q';
}
res.push_back(curRes); //保存结果
}
return res;
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<pair<int, int>>> allRes;
vector<pair<int, int>> curRes;
DFS(allRes, curRes, 0, n);
return resToString(allRes, n);
}
};
N皇后II
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens-ii
和上题思路一样，因为只需要返回解决方案的数量，所以不再保存结果，对符合条件的情况进行计数即可。
class Solution {
public:
void DFS(vector<pair<int, int>>& curRes, int curRow, int n, int& count)
{
//此时不需要保存结果, 计数就行
if(curRow == n)
{
++count;
}
for(int i = 0; i < n; i++)
{
//如果当前符合规则, 则继续, 如果不符合直接忽略
if(isVaild(curRes, curRow, i))
{
//记录当前行位置
curRes.push_back(make_pair(curRow, i));
//查找下一行
DFS(curRes, curRow + 1, n, count);
//回溯
curRes.pop_back();
}
}
}
bool isVaild(vector<pair<int, int>>& curRes, int row, int col)
{
//判断当前位置是否合法, 各皇后不能放在同一条直线上
for(const pair<int, int>& cur : curRes)
{
if(cur.first == row //判断当前行
|| cur.second == col //判断当前列
|| cur.first + cur.second == row + col //判断左对角线
|| cur.first - cur.second == row - col) //判断右对角线
{
return false;
}
}
return true;
}
int totalNQueens(int n) {
vector<pair<int, int>> curRes;
int count = 0;
DFS(curRes, 0, n, count);
return count;
}
};
最后
以上就是虚幻烧鹅最近收集整理的关于高级数据结构与算法 | 回溯算法（Back Tracking Method）回溯的全部内容，更多相关高级数据结构与算法内容请搜索靠谱客的其他文章。
发表评论 取消回复