深搜和回溯总结
基本概念
深搜
深度优先搜索（Depth First Search，DFS）属于图论中的概念。在图论中主要用于遍历树或者图上的节点，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次（一些详细的步骤和好看的图可以参考下边的几个链接）。而在搜索算法中主要通过递归方便地实现暴力枚举。
- https://en.wikipedia.org/wiki/Depth-first_search
- https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/
- https://www.algotree.org/algorithms/tree_graph_traversal/depth_first_search/
回溯
回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。回溯属于一种深搜的技巧，常常用在深搜中。
常见例题
自然数的拆分
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。
当n=7共14种拆分方法：
7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4 total=14
我们可以先将 7 拆分成 1+6，然后对 6 进行拆分，变成 1+5，依次类推，7 可以被拆分成 7=1+1+1+1+1+2。此处对于 2 的拆分有两种方式，首先1+1，然后尝试玩1打头之后，尝试2打头，还可以分成2+0（需要注意的是7不能取7=7）。
另外需要注意的是，按照此种方式，有7=3+4，此时4不可以被继续拆分，如果4被拆成1+1+1+1后，就成了7=3+1+1+1+1，与7=1+1+1+1+3重复所以我们发现一个规律，即被拆分成的数，总是升序的。也就是后边大，前边小，否则就会重复。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 3000
using namespace std;
int n,r;
int a[N];
void print(int step)
{
cout<<n<<"=";
for(int i=1;i<=step-1;i++)
cout<<a[i]<<"+";
cout<<a[step]<<endl;
}
void dfs(int sum,int step)
{
for(int i=a[step-1];i<=sum;i++)
{
if(i<n)
{
a[step]=i;
sum-=i;
if(sum==0)
print(step);
else
dfs(sum,step+1);
sum+=i;
}
}
}
int main()
{
cin>>n;
a[0]=1;
dfs(n,1);
return 0;
}
排列型枚举
全排列 I
给出一列互不相同的整数，返回其全排列。
这个问题我们相当于一开始有 n nn 位置，然后 n nn 个球，分别被标号 1 , 2 , … , n 1, 2, \dots , n1,2,…,n。我们一开始可以选择将 1 号球放入到第一个位置，然后将 2 号球放入到第二个位置，依次，，，最后将第 n nn 号球放到第 n nn 个位置，这样便完成了一个合法的排列。然后我们取出 n nn 号球，接着取出 n − 1 n-1n−1 号球，将 n nn 号球放到第 n − 1 n-1n−1 个位置，将第 n − 1 n-1n−1 号球放到第 n nn 个位置，这样便生成了一个新的排列。依次类推，便可以生成所有的排列。代码的思想也是一样的，如下：
class Solution {
public:
vector<int> path; // 相当于 n 个坑
vector<vector<int>> ans;
vector<bool> st; //记录每一个数是否被用过
vector<vector<int>> permutation(vector<int>& nums) {
st = vector <bool>(nums.size(), false);
path = vector<int>(nums.size());
dfs(nums, 0);
return ans;
}
// 每一层递归都是在未使用的球中选择一个新的球放到第 u 个位置
//递归的深度,初始为第0层
void dfs(vector<int>& nums, int u) {
if(u == nums.size()) {
ans.push_back(path);
return ;
}
//枚举每一个可以用的数
for(int i = 0; i < nums.size(); i ++) {
// 此处就决定了在未选择的球中进行选择
if(!st[i]) {
st[i] = true;
path[u] = nums[i];
dfs(nums, u + 1);
st[i] = false; // 这里就是回溯，恢复未使用的状态，此处也相当于把 i 号球从第 u 个位置拿走
}
}
}
};
注：此处是递归每个位置 u，选球 for 循环
全排列 II
给定一个可能包含重复项的数字集合nums，返回所有可能的唯一排列。
这个问题是全排列 I 的变体，由于包含重复数字，那么如果按照上述方法进行枚举，则有可能出现重复的排列。For example，上述取出 n nn 号球，取出 n − 1 n-1n−1 号球，将 n nn 号球放到第 n − 1 n-1n−1 个位置，将第 n − 1 n-1n−1 号球放到第 n nn 个位置的操作，如果 n − 1 n-1n−1 号球和 n nn 号球的标号一样，那么其实并没有生成新的排列，我们和上一次的排列是一样的。
这个问题如何解决呢，如果手动进行判重，那老麻烦了，这里有一个比较巧妙的方法，算法的过程如下：
- 先将所有数从小到大排序(特别重要)，使得相同的数会排在一起
- 我们对数无需判重,取而代之的是,枚举数的顺序是从前往后的,这里可以结合递归的层数的顺序实现，即数在选坑。
- 从左到右依次枚举每个数，每次将它放在一个空位上
- 我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 start，我们在枚举当前数时，只能枚举
start+1,start+2,…,nstart+1,start+2,…,n这些位置,在上一个数的后面，如果上一个数和当前数是不同的,那么当前数就可以从start = 0 开始选，选到没有被用过坑填入即可。
与 全排列 I 的变化是：全排列 I 递归每一个位置，尝试把每一个球放到该位置。全排列 II 递归每一个球，for 循环选择可以放该球的位置
**正确性：**我们知道按 全排列I 的方法产生的弊端是，会产生重复的排列，那么为什么 II 这样做就是对的呢，假设一个序列 1，2，3(1)，3(2)，4，5，如果不加限制，对于每一个球会尝试所有的位置（0-5），3（2）会跑到3（1）的前边，比如 1,2,3(2),3(1),4,5 这实际上和原序列就重复了。而我们加上第四步的限制后，就保证了3（2）不会跑到 3（1）前边，也就避免了重复。
class Solution {
public:
vector<int> path; //每一个坑填的数字是几
vector<vector<int>> ans;
vector<bool> st; //每一个坑是否被用过
vector<vector<int>> permutation(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 至关重要
st = vector<bool>(nums.size(), false);
path = vector<int>(nums.size()); //开出这么多坑
dfs(nums, 0, 0);
return ans;
}
//u->表示递归到第几个坑
//start->从哪个坑开始填起
void dfs(vector<int> & nums, int u, int start)
{
if(u == nums.size())
{
ans.push_back(path);
return ;
}
for(int i = start; i < nums.size(); i ++)
{
if(!st[i])
{
st[i] = true;
path[i] = nums[u];
if(u + 1 < nums.size() && nums[u] == nums[u + 1])
dfs(nums, u + 1, i + 1);
// 二是，如果前后两个元素不相等
else // 双重含义，一所有坑都被填满了,已经指向最后一个元素
dfs(nums, u + 1, 0);
st[i] = false; //还原现场
}
}
}
};
注：此处是递归每个球 u，选位置 for 循环，开始位置 start
组合型枚举
组合 I
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
这个还比较简单，相当于 m 个位置，每一个位置，对未选择的数进行选或不选的操作就行，同样为了防止重复，第 i 次，选择了 j，第 i+1 次，只能从 j+1 及之后进行选择，因为（2，3）和（3，2）是同一组组合。这种处理方式和 全排列 II 避免重复的处理方式一致。
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int a[N];
int n, m;
void dfs(int u, int start)
{
if(u > m)
{
for(int i = 1; i <= m; i ++)
{
printf("%d ", a[i]);
}
puts("");
return ;
}
for(int i = start; i <= n; i ++)
{
a[u] = i;
dfs(u + 1, i + 1);
}
}
int main()
{
cin >> n >> m;
dfs(1, 1);
return 0;
}
组合 II
给定一个长度为 n 的可包含重复数字的序列，从中随机选取 m 个数字，输出所有可能的选择方案。
先 mark 一下，丢份题解，一时没看明白，[\touda]
N皇后问题
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。间不能直接吃掉对方。要求输出所有的可行解
经典题了，解法很多，这里只贴最原始的深搜解法。
class Solution {
private char[][] map;
private int size;
private List<List<String>> list = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
map = new char[n + 5][n + 5];
size = n;
initMap();
putQueens(0);
return list;
}
/**
* 初始化地图
*/
public void initMap(){
for(int i = 0; i < size; ++i){
for(int j = 0; j < size; ++j){
map[i][j] = '.';
}
}
}
/**
* 放置皇后
* @param row 表示放的是第几行,从 0 开始，到 (size - 1) 行结束
*/
public void putQueens(int row){
if(row == size){
List<String> tmpList = new ArrayList<>();
for(int i = 0; i < size; ++i){
tmpList.add(new String(map[i], 0, size));
}
list.add(tmpList);
return;
}
for(int i = 0; i < size; ++i){
if(Judge(row, i)){
map[row][i] = 'Q';
putQueens(row + 1);
map[row][i] = '.';
}
}
return;
}
/**
* 判断当前位置是否可以放皇后
* @param row 行
* @param col 列
* @return 是否可以放皇后
*/
public boolean Judge(int row, int col){
//判断上方
for(int i = row - 1; i >= 0; --i){
if(map[i][col] == 'Q'){
return false;
}
}
//判断左上
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j){
if(map[i][j] == 'Q'){
return false;
}
}
//判断右上
for(int i = row - 1, j = col + 1; i >= 0 && j < size; --i, ++j){
if(map[i][j] == 'Q'){
return false;
}
}
return true;
}
}
一些简单的树和图上的问题
二叉树的遍历
题目链接：
// 前序
class Solution {
public:
vector<int> ans;
void pre_traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
ans.push_back(root->val);
pre_traverse(root->left);
pre_traverse(root->right);
return;
}
vector<int> preorderTraversal(TreeNode* root) {
ans.clear();
pre_traverse(root);
return ans;
}
};
// 中序
class Solution {
public:
void dfs(TreeNode *root, vector<int>& ans) {
if (root == nullptr) return;
dfs(root->left, ans);
ans.push_back(root->val);
dfs(root->right, ans);
return;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
ans.clear();
dfs(root, ans);
return ans;
}
};
// 后序
class Solution {
public:
void dfs(TreeNode *root, vector<int>& ans) {
if (root == nullptr) return;
dfs(root->left, ans);
dfs(root->right, ans);
ans.push_back(root->val);
return;
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
ans.clear();
dfs(root, ans);
return ans;
}
};
二叉树的所有路径
给你一个二叉树的根节点
root，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
就是树的前序遍历，每次将经过的节点记录，到达叶子节点的时候，将答案统计一下。
class Solution {
vector<string> ans;
vector<int> stack;
public:
void dfs(TreeNode* root) {
stack.push_back(root->val);
if (root && root->left == nullptr && root->right == nullptr) {
string tmp = "";
for (int i = 0; i < stack.size() - 1; ++i) {
tmp += to_string(stack[i]);
tmp += "->";
}
tmp += to_string(stack.back());
ans.push_back(tmp);
return;
}
if (root && root->left) {
dfs(root->left);
if (stack.size()) stack.pop_back();
}
if (root && root->right) {
dfs(root->right);
if (stack.size()) stack.pop_back();
}
return;
}
vector<string> binaryTreePaths(TreeNode* root) {
ans.clear();
stack.clear();
if (root) dfs(root);
return ans;
}
};
岛屿的最大面积
我们想知道网格中每个连通形状的面积，然后取最大值。如果我们在一个土地上，以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0。这样我们就不会多次访问同一土地。
class Solution {
int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
return 0;
}
grid[cur_i][cur_j] = 0;
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};
int ans = 1;
for (int index = 0; index != 4; ++index) {
int next_i = cur_i + di[index], next_j = cur_j + dj[index];
ans += dfs(grid, next_i, next_j);
}
return ans;
}
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i != grid.size(); ++i) {
for (int j = 0; j != grid[0].size(); ++j) {
ans = max(ans, dfs(grid, i, j));
}
}
return ans;
}
};