回溯策略
我个人其实把回溯看做递归的一个应用，回溯简单来讲就是用递归的方式深度遍历所有的可能，而在某些可能是一个解的时候，就记录，这目前看来和回溯两个字没啥关系，问题就在于，回溯可以解决一些需要我们回退元素并继续尝试的问题。
刚才的概念里包含了两个关键词：“回退”，“尝试”。
全排列举例
比如拿全排列来举例，全排列就是给你一串数字（我们假定简单情况，没有数字重复），要你写出所有的排列组合的可能，就是全排列。那么我们用什么办法能找到所有的排列组合呢？
思路是这样的：
先固定第一个数，再固定第二个数，再固定，再固定，直到还剩一个数，那么，把最后一个数加上去，全排列的第一个解就得到了，然后呢，我们往回退！，推到还剩两个数的时候，把另一个数放进去，再放之前的倒数第二个数，这就是第二解，再然后呢，再退，再重放，那么再重放的时候，无论2个还是3个，都要保证不能再出现已经得到的解，那么这个时候尝试的意义就来了，先试一下，如果这个方式被用过了，那就不用这个，我们只用没尝试过的解。
那这种类型的问题，都可以用回溯来解决。
回溯模板
回溯的模板，首先肯定是递归，递归思想一看就晕的看我上一篇随笔递归思想以及晕递归的解决方案 - ThirteenQ - 博客园 (cnblogs.com)
另外回溯的模板我是从13.1 回溯算法 - Hello 算法 (hello-algo.com)里学的，感兴趣的小伙伴去看原文吧。这里我的讲解只能起到辅助作用。
我们在这里设定一个state 和choices 分别表示目前存储的状态和即将面临的选择，当然参数里肯定还要加一个存储结果的结构res 另外在尝试的过程中，如何判断是否是第一次尝试，或者是否是不满足某种约束，就增加一个约束的结构，这里全排列的话就是selected ，这个过程也是回溯概念里的剪枝。
好啦，话不多说，下面上代码（这个是力扣题目：https://leetcode.cn/problems/VvJkup/description/
class Solution {
public:
void backTrack(vector<int>& state, const vector<int>& choices, vector<bool>& selected, vector<vector<int>>& res) {
if(state.size() == choices.size()) {
res.push_back(state);
}
for(int i = 0; i < choices.size(); ++i) {
int choice = choices[i];
if(selected[i]) {
selected[i] = false;
state.push_back(choice);
backTrack(state, choices, selected, res);
selected[i] = true;
state.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> selected(nums.size(), true);
vector<int> state;
vector<vector<int>> res;
backTrack(state, nums, selected, res);
return res;
}
};
还有hello算法这本书里的第一个例子的问题三，我这里贴上我写的完整的代码。
// 问题描述：要求在二叉树中搜索值为7的点，返回根节点到所有值为7的点的路径，并要求路径中不包含值为3的节点。
#include <iostream>
#include <vector>
using namespace std;
class TreeBinary {
public:
int val;
TreeBinary* left;
TreeBinary* right;
TreeBinary(int x) : val(x), left(nullptr), right(nullptr) {}
};
bool isSolution(vector<TreeBinary* >& state) {
return !state.empty() && state.back()->val == 7;
}
bool isValid(vector<TreeBinary* >& state, TreeBinary* choice) {
return choice != nullptr && choice->val != 3;
}
void recordSolution(vector<TreeBinary* >& state, vector<vector<TreeBinary* >>& res) {
res.push_back(state);
}
void makeChoice(vector<TreeBinary* >& state, TreeBinary* choice) {
state.push_back(choice);
}
void reset(vector<TreeBinary* >& state) {
state.pop_back();
}
void backTrack(vector<TreeBinary* >& state, vector<TreeBinary* >& choices, vector<vector<TreeBinary* >>& res) {
if(isSolution(state)) {
recordSolution(state, res);
}
for(auto& choice : choices) {
if(isValid(state, choice)) {
makeChoice(state, choice);
vector<TreeBinary* > nextChoice = {choice->left, choice->right};
backTrack(state, nextChoice, res);
reset(state);
}
}
}
vector<TreeBinary* > state;
void preOrder(TreeBinary* root) {
if(root == nullptr) {
return;
}
state.push_back(root);
preOrder(root->left);
preOrder(root->right);
}
int main() {
/* 构建树 */
TreeBinary* root = new TreeBinary(1);
TreeBinary* tree1 = new TreeBinary(7);
TreeBinary* tree2 = new TreeBinary(3);
TreeBinary* tree3 = new TreeBinary(4);
TreeBinary* tree4 = new TreeBinary(5);
TreeBinary* tree5 = new TreeBinary(6);
TreeBinary* tree6 = new TreeBinary(7);
TreeBinary* tree7 = new TreeBinary(7);
root->left = tree1;
root->right = tree2;
tree1->left = tree3;
tree1->right = tree4;
tree2->left = tree5;
tree2->right = tree6;
tree3->left = tree7;
/* 开始回溯 */
vector<TreeBinary* > choices = {root};
vector<vector<TreeBinary* >> res;
backTrack(state, choices, res);
for(auto& ress: res) {
for(auto& i : ress) {
cout << i->val << "-";
}
cout << endl;
}
return 0;
}