其实回溯算法和 DFS 算法非常类似，本质上就是一种暴力穷举算法。回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」。
解决一个回溯问题，实际上就是一个决策树的遍历过程，站在回溯树的一个节点上，只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
算法框架：
1
2
3
4
5
6
7
8
9
10
| result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
|
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
形式一、元素无重不可复选
即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。
集合
通过保证元素之间的相对顺序不变来防止出现重复的子集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<vector<int>> ans;
void backtracking(vector<int>& nums, vector<int>& path, int start) {
ans.push_back(path);
for(int i = start; i < nums.size();i ++) {
path.push_back(nums[i]);
backtracking(nums, path, i + 1);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> path;
backtracking(nums, path, 0);
return ans;
}
};
|
大小为 k 的组合就是大小为 k 的子集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backtracking(int n, int k, int start) {
if(path.size() == k) {
ans.push_back(path);
}
for(int i = start; i <= n;i ++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return ans;
}
};
|
排列
可以使用used数据来标识哪些元素已经用过了，也可以使用swap将使用过的数据往前放，后面的就是未使用过的元素了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<vector<int>> result;
vector<bool> used;
void backtracking(vector<int>& nums, vector<int>& path) {
if(path.size() == nums.size()) {
result.push_back(path);
return;
}
for(int i = 0; i < nums.size();i++) {
if(used[i] == true) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, path);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> path;
used.resize(nums.size(), false);
backtracking(nums, path);
return result;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<vector<int>> result;
void backtracking(vector<int>& nums, vector<int>& path, int startIndex) {
if(path.size() == nums.size()) {
result.push_back(path);
return;
}
for(int i = startIndex; i < nums.size();i++) {
path.push_back(nums[i]);
swap(nums[i], nums[startIndex]);
backtracking(nums, path, startIndex + 1);
swap(nums[i], nums[startIndex]);
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> path;
backtracking(nums, path, 0);
return result;
}
};
|
岛屿问题
岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组
如果你把二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构。
DFS代码框架如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void traverse(TreeNode* root) {
traverse(root->left);
traverse(root->right);
}
void dfs(vector<vector<int>> grid, int i, int j, vector<vector<bool>> visited) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || j < 0 || i >= m || j >= n) {
return;
}
if (visited[i][j]) {
return;
}
visited[i][j] = true;
dfs(grid, i - 1, j, visited);
dfs(grid, i + 1, j, visited);
dfs(grid, i, j - 1, visited);
dfs(grid, i, j + 1, visited);
}
|