[leetcode]回溯法
零.参考视频！安利！！！
带你学透回溯算法（理论篇）| 回溯法精讲！_哔哩哔哩_bilibili
一.回溯法可以解决的问题（都可以抽象为一个树形结构）
1.排列
2.组合
3.分割
4.子集
5.棋盘
二.回溯法的模板
我的理解：
1.首先命名函数名为backtracking
2.按需求放入需要的参数
3.回溯算法是离不开递归的，而递归算法必要的就是它的退出条件
if(终止条件)
{
收集结果
return;
}
4.处理完这一层的数据之后，我们要处理下面的节点
for(节点元素)
{
处理节点
5.处理完当前节点后需要递归到下一层
for(节点元素)
{
处理节点
递归函数
6.我们找寻找我们需要的结果的时候，遇到需要回溯的情形了，我们要进行对应的回溯
for(节点元素)
{
处理节点
递归函数
回溯操作
}
vector<> res; // 用于存放最后结果
vector<> path; // 用于存放每一次最外层 for 循环产生的结果
void backtracking(参1:题目中的数组,参2:结束循环的变量,参3:第n层 for 循环从谁开始，也就是子数组的开始位置，是一直变化的) { // 参数中要有一个值控制树的深度
if (终止条件) {
// 这里控制 for 循环是几重 for 循环，并返回上一层 for 循环
存放结果; // 将哪些变量添加到 res
return;
}
for (int i = 子数组在哪开始;i<要对哪些数进行遍历，并进行相关剪枝操作;i++) { // 控制最外层 for 循环递归多少次
// TODO 该元素在 push 之前的相关操作
path.push_back(i); // 将 i 添加到 path 中
backtracking(参1:题目中的数组,参2:结束循环的变量,参3:第n层 for 循环从谁开始); // 递归
// TODO 该元素在弹出之前的相关操作
path.pop_back();
}
}
三.具体问题
3.1全排列问题（因为可以重复选取，所以使用used数组）
问题描述
给定一个整数 n，生成由 1 到 n 组成的所有不重复的数字序列，每行一个序列，每个数字保留 5 个场宽。
输入输出样例
-
输入：
3 -
输出：
复制
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
解题思路
这是一个典型的全排列问题，可以通过回溯法解决。具体步骤如下：
-
使用深度优先搜索（DFS）逐步构建排列。
-
使用一个标记数组
hx来记录每个数字是否已经被使用，避免重复选择。 -
在递归过程中，每次选择一个未使用的数字加入当前排列，并递归调用。
-
递归返回后，取消标记，以便尝试其他可能的排列。
Coding:蓝桥杯模板：排列型模板
//生成从1到n的全排列
Coding:
#include<iostream>
using namespace std;
int n;//共计n个数
int order[20];
bool chosen[20];
void calc(int k)//生成从 1 到 n 的所有全排列
{
if (k == n + 1)//递归终止条件
{
for (int i = 1;i <= n;i++)
{
cout << order[i] << "";
}
puts("");
return;
}
for (int i = 1;i <= n;i++)//尝试所有可能的数字
{
if (chosen[i])//检查数字是否已被使用
{
continue;
}
order[k] = i;//选择数字并标记
chosen[i] = 1;
calc(k + 1);//递归生成下一个位置的排列
chosen[i] = 0;//回溯操作
order[k] = 0;
}
}
int main()
{
// 从用户输入中读取 n 的值
cout << "请输入 n 的值: ";
cin >> n;
// 从第一个位置开始生成排列
calc(1);
return 0;
}
Coding:DFS搜索回溯算法
谢谢卡尔老师！！！！！！！！
bilibili:
组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili
代码随想录：
Coding:
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue; // path里已经收录的元素，直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
int main() {
Solution sol;
vector<int> nums = { 1, 2, 3 }; // 定义输入数组
vector<std::vector<int>> permutations = sol.permute(nums);
// 输出所有排列
for (const auto& perm : permutations) {
for (int num : perm) {
cout << num << " ";
}
cout << std::endl;
}
return 0;
}
过程展示：
3.2组合问题(startIndex是在剩下的部分进行选择/切割)
notice:
satrtIndex在这里就是起始的数字
bilibili:
带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili
Coding edition1:Letcode77
#include <iostream>
#include <vector>
using namespace std;
class Solution {
private:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果
void backtracking(int n, int k, int startIndex) {//n，k代表从n个数据中选取k个数据做组合
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i); // 处理节点
backtracking(n, k, i + 1); // 递归
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
result.clear(); // 可以不写
path.clear(); // 可以不写
backtracking(n, k, 1);
return result;
}
};
int main() {
int n = 4; // 元素总数
int k = 2; // 要选取的元素个数
Solution sol;
vector<vector<int>> combinations = sol.combine(n, k);
// 输出所有组合
for (const auto& comb : combinations) {
cout << "[";
for (int i = 0; i < comb.size(); ++i) {
if (i > 0) {
cout << ", ";
}
cout << comb[i];
}
cout << "]" << endl;
}
return 0;
}
result:
Coding edition2:自己的方法
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int> nums,vector<int>& path ,vector<vector<int>>& result,int startIndex,int k)
{
if (path.size() == k)
{
result.push_back(path);
return;
}
for (int i = startIndex;i < nums.size();i++)
{
path.push_back(nums[i]);
backtracking(nums, path, result, i + 1, k);
path.pop_back();
}
}
int main() {
vector<int> nums{ 1,2,3,4 };
int startIndex = 0;
int k = 2;//k代表从nums中取出k个数做组合
backtracking(nums, path, result, startIndex,k);
// 输出结果
for (const auto& comb : result) {
for (int num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
result:
3.3分割回文串问题（同理为了在剩下的字符串中进行切割，我们需要使用StartIndex进行控制）
代码随想:
代码随想录
notice:
startIndex在这里就是切割的那条分割线,所以我们要知道，在[startIndex,i]的这个区间里就是截取后剩下的字串。
harvest:为什么[startIndex,i]就是一个子串呢？
for(int i = startIndex;i < s.size();i++) 注意在这个for循环中， i最开始是startIndex，但是在每一次的for循环之中，i每++1次，就相当于后面的一个一位的子串，然后虽然会递归进层，但是最终还是会返回这个现场的for循环，判断长度为2，为3........的子串的。我们在这里进行一个剪枝操作，会比在收集结果的时候进行剪枝在时间上好很多。（实在不懂的，看卡尔老师的视频的第17分钟，卡尔老师的视频链接：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！_哔哩哔哩_bilibili）
Coding:
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<vector<string>> result;
vector<string> path;
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
void backtracking(const string s, int startIndex)
{
if (s.size() == startIndex)
{
result.push_back(path);
return;
}
for (int i = startIndex;i < s.size();i++)
{
if (isPalindrome(s, startIndex, i))
{
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
}
else
{
continue;
}
backtracking(s, i + 1);
path.pop_back();
}
}
int main()
{
string s = "aab";
backtracking(s, 0);
for (auto& comb : result) {
for (string num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}