一、经验总结
在递归算法中某些变量需要在回溯到上一层递归后恢复现场（如递归路径），恢复现场的方法有：
- 全局变量手动恢复：如果该变量的类型为自定义类型（vector, string等）则推荐定义为全局变量。如果将自定义类型数据作为函数参数进行传递（局部变量），那么每层递归都要进行构造和析构工作，消耗很大。定义为全局变量则不存在这个问题，但是全局变量需要在回溯到上一层后手动进行现场恢复；
- 局部变量自动恢复：如果该变量的类型为内置类型（int, double等）则推荐定义为函数参数（局部变量）。内置类型数据的创建和拷贝消耗相比手动恢复现场几乎可以忽略不记。如果该变量为局部变量（局部参数），则每层递归的变量都是全新、独立的变量不会相互影响，在回溯过程中能够自动实现“恢复现场”。
剪枝优化的方法有：
- 对于全排列题目使用全局或局部标记进行剪枝：全排列Ⅰ（全局标记）、全排列Ⅱ（局部标记）；可以使用一些巧妙地方式构建哈希映射，如题目：N皇后（斜线映射）、解数独（区块映射）
- 对于具有无序性的集合，从当前位置的下一个位置向下递归：找子集、组合
- 对于具有特定约束条件的问题，根据其他特殊规则进行剪枝：括号生成（左右括号的数量关系）
二、相关编程题
2.1 找出所有子集的异或总和再求和
题目链接
1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
int sum;
int XOR;
public:
int subsetXORSum(vector<int>& nums) {
DFS(nums,0);
return sum;
}
void DFS(vector<int>& nums, int pos)
{
sum+=XOR;
for(int i = pos; i < nums.size(); ++i)
{
XOR^=nums[i];
DFS(nums, i+1);
XOR^=nums[i]; //回溯恢复现场：异或消消乐
}
}
};
2.2 全排列Ⅱ
题目链接
47. 全排列 II - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
vector<vector<int>> ret;
vector<int> path;
bool used[8];
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
DFS(nums, 0);
return ret;
}
void DFS(vector<int>& nums, int pos)
{
if(pos == nums.size())
{
ret.push_back(path);
return;
}
unordered_set<int> hash; //局部的哈希表
for(int i = 0; i < nums.size(); ++i)
{
if(!used[i] && !hash.count(nums[i]))
{
hash.insert(nums[i]);
path.push_back(nums[i]);
used[i] = true;
hash.insert(nums[i]);
DFS(nums, pos+1);
path.pop_back();
used[i] = false;
}
}
}
};
2.3 电话号码的字母组合
题目链接
17. 电话号码的字母组合 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
vector<string> ret;
string path;
string strs[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
vector<string> letterCombinations(string digits) {
if(digits.size() == 0) return ret;
DFS(digits, 0);
return ret;
}
void DFS(string& digits, int pos)
{
if(pos == digits.size())
{
ret.push_back(path);
return;
}
string &str = strs[digits[pos]-'0'];
for(int i = 0; i < str.size(); ++i)
{
path.push_back(str[i]);
DFS(digits, pos+1);
path.pop_back();
}
}
};
2.4 括号生成
题目链接
22. 括号生成 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
vector<string> ret;
string path;
int left, right;
public:
vector<string> generateParenthesis(int n) {
DFS(n);
return ret;
}
void DFS(int n)
{
if(right == n)
{
ret.push_back(path);
return;
}
if(left < n) //可以添加左括号
{
path.push_back('(');
++left;
DFS(n);
path.pop_back(); //恢复现场
--left;
}
if(right < left) //可以添加右括号
{
path.push_back(')');
++right;
DFS(n);
path.pop_back(); //恢复现场
--right;
}
}
};
2.5 组合
题目链接
77. 组合 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
vector<vector<int>> ret;
vector<int> path;
int _k;
public:
vector<vector<int>> combine(int n, int k) {
_k = k;
DFS(n, 1);
return ret;
}
void DFS(int n, int pos)
{
if(path.size() == _k)
{
ret.push_back(path);
return;
}
for(int i = pos; i <= n; ++i)
{
path.push_back(i);
DFS(n, i+1);
path.pop_back();
}
}
};
2.6 目标和
题目链接
494. 目标和 - 力扣（LeetCode）
题目描述
算法原理
编写代码
//path是全局变量（超时）：
class Solution {
int _target, sum, ret;
public:
int findTargetSumWays(vector<int>& nums, int target) {
_target = target;
DFS(nums, 0);
return ret;
}
void DFS(vector<int>& nums, int pos)
{
if(pos == nums.size())
{
if(sum == _target) ++ret;
return;
}
//+
sum+=nums[pos];
DFS(nums, pos+1);
sum-=nums[pos];
//-
sum-=nums[pos];
DFS(nums, pos+1);
sum+=nums[pos];
}
};
//path是函数参数（更优）：
class Solution {
int _target, ret;
public:
int findTargetSumWays(vector<int>& nums, int target) {
_target = target;
DFS(nums, 0, 0);
return ret;
}
void DFS(vector<int>& nums, int pos, int sum)
{
if(pos == nums.size())
{
if(sum == _target) ++ret;
return;
}
//+
DFS(nums, pos+1, sum+nums[pos]);
//-
DFS(nums, pos+1, sum-nums[pos]);
}
};
2.7 组合总和
题目链接
39. 组合总和 - 力扣（LeetCode）
题目描述
算法原理
编写代码
//解法一：
class Solution {
vector<vector<int>> ret;
vector<int> path;
int _target;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
DFS(candidates, 0, 0);
return ret;
}
void DFS(vector<int>& arr, int pos, int sum)
{
if(sum >= _target)
{
if(sum == _target)
ret.push_back(path);
return;
}
for(int i = pos; i < arr.size(); ++i)
{
path.push_back(arr[i]);
DFS(arr, i, sum+arr[i]); //一个数字可以选择多次，从当前选中的位置i开始向后遍历递归
path.pop_back();
}
}
};
//解法二：
class Solution {
vector<vector<int>> ret;
vector<int> path;
int _target;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
DFS(candidates, 0, 0);
return ret;
}
void DFS(vector<int>& arr, int pos, int sum)
{
if(sum == _target)
{
ret.push_back(path);
return;
}
if(sum > _target || pos == arr.size()) return;
int i = 0;
while(sum+i*arr[pos] <= _target) //等于也要向下递归
{
if(i>0) path.push_back(arr[pos]); //出现0次不需要添加数字
DFS(arr, pos+1, sum+i*arr[pos]);
++i;
}
//恢复现场
while(--i) //出现0次不需要添加数字
{
path.pop_back();
}
}
};
2.8 字母大小写全排列
题目链接
784. 字母大小写全排列 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
vector<string> ret;
string path;
public:
vector<string> letterCasePermutation(string s) {
DFS(s, 0);
return ret;
}
void DFS(string &s, int pos)
{
if(pos == s.size())
{
ret.push_back(path);
return;
}
//不变
path.push_back(s[pos]);
DFS(s, pos+1);
path.pop_back();
//变
if(isalpha(s[pos]))
{
path.push_back(s[pos]^32);
DFS(s, pos+1);
path.pop_back();
}
}
};
2.9 优美的排列
题目链接
526. 优美的排列 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
int ret;
bool used[16];
public:
int countArrangement(int n) {
DFS(n, 1);
return ret;
}
void DFS(int n, int pos)
{
if(pos == n+1)
{
++ret;
return;
}
for(int i = 1; i <= n; ++i)
{
if(!used[i] && (i%pos==0 || pos%i==0))
{
used[i] = true;
DFS(n, pos+1);
used[i] = false;
}
}
}
};
2.10 N皇后
题目链接
51. N 皇后 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
vector<vector<string>> ret;
vector<string> path;
bool col[9];
bool slant1[17], slant2[17]; //正斜线和反斜线哈希表
public:
vector<vector<string>> solveNQueens(int n) {
path.resize(n, string(n, '.'));
DFS(n, 0);
return ret;
}
void DFS(int n, int row)
{
if(row == n)
{
ret.push_back(path);
return;
}
for(int i = 0; i < n; ++i)
{
//选中位置的下标[row, i]
int k1 = row-i+(2*n-1)/2; //正斜线的下标
int k2 = row+i; //反斜线的下标
if(!col[i] && !slant1[k1] && !slant2[k2])
{
col[i] = slant1[k1] = slant2[k2] = true;
path[row][i] = 'Q';
DFS(n, row+1);
// 恢复现场
col[i] = slant1[k1] = slant2[k2] = false;
path[row][i] = '.';
}
}
}
};
2.11 有效的数独
题目链接
36. 有效的数独 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool row[9][10] = {false};
bool col[9][10] = {false};
bool block[3][3][10] = {false};
int n = board.size();
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(board[i][j] != '.')
{
int num = board[i][j]-'0';
if(row[i][num] || col[j][num] || block[i/3][j/3][num])
{
return false;
}
else
{
row[i][num] = col[j][num] = block[i/3][j/3][num] = true;
}
}
}
}
return true;
}
};
2.12 解数独
题目链接
37. 解数独 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
bool checkRow[9][10];
bool checkCol[9][10];
bool checkBlock[3][3][10];
int n;
public:
void solveSudoku(vector<vector<char>>& board) {
n = board.size();
//预处理，将已有的数字添加到各哈希表
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(board[i][j] != '.')
{
int k = board[i][j]-'0';
checkRow[i][k] = checkCol[j][k] = checkBlock[i/3][j/3][k] = true;
}
}
}
//从0，0位置开始进行递归
DFS(board, 0, 0);
}
bool DFS(vector<vector<char>>& board, int row, int col)
{
int j = col;
for(int i = row; i < n; ++i)
{
for(; j < n; ++j)
{
if(board[i][j] == '.')
{
for(int k = 1; k <= 9; ++k)
{
if(!checkRow[i][k] && !checkCol[j][k] && !checkBlock[i/3][j/3][k])
{
checkRow[i][k] = checkCol[j][k] = checkBlock[i/3][j/3][k] = true;
board[i][j] = k+'0';
if(!DFS(board, i, j))
{
//如果当前选择的数字使得后续的填写无法继续，恢复现场，重新选择数字
checkRow[i][k] = checkCol[j][k] = checkBlock[i/3][j/3][k] = false;
board[i][j] = '.';
}
else
//如果当前选择的数字使得后续填写完成，直接返回true。
return true;
}
}
return false; //9个数字都试过不行，返回false
}
}
j = 0; //注意这里的写法，一行遍历完j还是要还原为0
}
//将所有的空格填写完，返回true
return true;
}
};
2.13 单词搜索
题目链接
79. 单词搜索 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int m, n;
bool used[6][6];
public:
bool exist(vector<vector<char>>& board, string word) {
m = board.size(), n = board[0].size();
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(board[i][j] == word[0])
{
used[i][j] = true;
if(DFS(board, i, j, word, 0))
return true;
used[i][j] = false;
}
}
}
return false;
}
bool DFS(vector<vector<char>>& board, int r, int c, string word, int pos)
{
if(pos == word.size()-1) return true;
for(int i = 0; i < 4; ++i)
{
int x=r+dx[i], y=c+dy[i];
if(x>=0 && x<m && y>=0 && y<n && !used[x][y] && board[x][y] == word[pos+1])
{
used[x][y] = true;
if(DFS(board, x, y, word, pos+1))
return true;
used[x][y] = false;
}
}
return false;
}
};
2.14 黄金矿工
题目链接
1219. 黄金矿工 - 力扣（LeetCode）
题目描述
算法原理
从每一个非零位置开始进行一次DFS，当一条路径走到尽头时更新一次结果（统计最大值）
编写代码
class Solution {
int ret;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int visited[15][15];
int m, n;
public:
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)
{
visited[i][j] = true;
DFS(grid, i, j, grid[i][j]);
visited[i][j] = false;
}
}
}
return ret;
}
void DFS(vector<vector<int>>& grid, int r, int c, int sum)
{
bool flag = false;
for(int i = 0; i < 4; ++i)
{
int x=r+dx[i], y=c+dy[i];
if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && grid[x][y]!=0)
{
flag = true;
visited[x][y] = true;
DFS(grid, x, y, sum+grid[x][y]);
visited[x][y] = false;
}
}
if(!flag) ret = max(ret, sum); //一条路径走到头更新结果
}
};
2.15 不同路径Ⅲ
题目链接
980. 不同路径 III - 力扣（LeetCode）
题目描述
算法原理
从数字1开始进行DFS，当递归遍历到数字2时，检查一下路径中0的个数：如果通过了所有0，证明是一条合法的路径，记录不同路径的数目；否则不进行记录。
编写代码
class Solution {
int ret;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int visited[20][20];
int m, n, step=1;
public:
int uniquePathsIII(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
int r = 0, c = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == 1)
r=i, c=j;
else if(grid[i][j] == 0)
++step;
}
}
visited[r][c] = true;
DFS(grid, r, c, 0);
return ret;
}
void DFS(vector<vector<int>>& grid, int r, int c, int cnt)
{
if(grid[r][c] == 2)
{
if(step == cnt) ++ret;
return;
}
for(int i = 0; i < 4; ++i)
{
int x=r+dx[i], y=c+dy[i];
if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && grid[x][y]!=-1)
{
visited[x][y] = true;
DFS(grid, x, y, cnt+1);
visited[x][y] = false;
}
}
}
};
