题目链接：491.递增子序列 思路：和子集那道题思路很像，每次在数组中选择一个数，选过的数不能选择，这里要求集合数量必须大于2个才能符合，仍然需要去重，但这里选额的是子序列，数组不能进行排序，故去重使用集合，记录当前回溯函数选择过的数，遇到选择过的数不需要再重新选择 代码： class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> tmp;
int n = nums.size();
auto dfs = [&](auto&& dfs, int i) {
if(i > n) // 终止条件
return;
if(tmp.size() >= 2) // 符合题目条件加入答案中
ans.push_back(tmp);
set<int> cnt; // 集合去重，每次回溯函数，同一个数只选择一次
for(int j = i; j < n; ++j) {
if(!tmp.empty() && nums[j] < tmp.back()) // 每次选择的数必须是递增的
continue;
if(!cnt.count(nums[j])) {
tmp.push_back(nums[j]);
dfs(dfs, j + 1);
tmp.pop_back();
cnt.insert(nums[j]);
}
}
};
dfs(dfs, 0);
return ans;
}
};
题目链接：46.全排列 思路：全排列思路仍然是每次从数组中选择一个数，选过的数不能再选，因为全排列的特殊性，排列长度和数组长度一样，故不需要额外创建数组来记录每次选择结果，每次将选择的数和当前应该选择的位置上的数交换即可 代码： class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
int n = nums.size();
vector<int> tmp;
auto dfs = [&](auto&& dfs, int i) {
if(i == n) {
ans.push_back(nums); // 选择成功加入到ans中
return;
}
for(int j = i; j < n; ++j) {
swap(nums[i], nums[j]); // 选择 nums[j]，将它和nums[i] 交换
dfs(dfs, i + 1);
swap(nums[i], nums[j]); // 再交换回来
}
};
dfs(dfs, 0); // 从0开始选择
return ans;
}
};
题目链接：47.全排列 II 思路：思路和上一题一致，这里需要去重，即相同的数，只能选择一次，去重方法和子序列那题类似，使用集合去重 代码： class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
int n = nums.size();
vector<int> tmp;
auto dfs = [&](auto&& dfs, int i) {
if(i == n) {
ans.push_back(nums);
return;
}
set<int> cnt; // 集合去重
for(int j = i; j < n; j++) {
if(cnt.count(nums[j]) != 0) // 去重
continue;
swap(nums[i], nums[j]); // 交换
dfs(dfs, i + 1);
swap(nums[i], nums[j]); // 交换
cnt.insert(nums[j]); // 选择的数加入到集合中
}
};
dfs(dfs, 0); // 从0开始
return ans;
}
};
题目链接：332.重新安排行程 思路：本题没有完整的思路，一刷感觉思路不完善，这里使用的是卡哥的代码，二刷的时候仔细思考，卡哥讲解 代码： class Solution {
private:
// unordered_map<出发城市, map<到达城市, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
if (result.size() == ticketNum + 1) {
return true;
}
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
if (target.second > 0 ) { // 使用int字段来记录到达城市是否使用过了
result.push_back(target.first);
target.second--;
if (backtracking(ticketNum, result)) return true;
result.pop_back();
target.second++;
}
}
return false;
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
vector<string> result;
for (const vector<string>& vec : tickets) {
targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK");
backtracking(tickets.size(), result);
return result;
}
};
题目链接：51.N皇后 思路：
N皇后经典题目，使用回溯算法，每次选择一个位置放入皇后，当不符合的时候回溯选择其他位置； 使用数组arr，记录每行选择的皇后的列的位置，从第0行开始回溯，每次回溯代表着选择某一行选择某一列放置皇后； 使用judge函数判断当前位置是否可以放置皇后； GetRow函数获取每行的字符串形式； 代码： class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> row;
vector<int> arr(n, 0); // 存储每一行放的皇后的列数
auto judge = [&](int t) ->bool {
for(int i = 0; i < t; ++i) {
// 判断是否有皇后在同一列，判断皇后是否在斜线上，即横坐标距离，于纵坐标之间的距离是否相等
if(arr[i] == arr[t] || abs(t - i) == abs(arr[t] - arr[i]))
return false;
}
return true;
};
auto GetRow = [&](int k) -> string { // 将某一行转换为字符串
stringstream ss;
for(int i = 0; i < n; ++i) {
if(i == k)
ss << 'Q';
else
ss << '.';
}
return ss.str();
};
auto dfs = [&](auto&& dfs, int i) {
if(i == n) {
ans.push_back(row); // 符合放入答案中
return;
}
for(int j = 0; j < n; ++j) { // 每行选择某一列放置皇后
arr[i] = j; // 第i行选择将皇后放到第 j 列， 即[i, j]的位置
if(judge(i)) { // 判断皇后位置是否合法
row.push_back(GetRow(j));
dfs(dfs, i + 1);
row.pop_back();
}
}
};
dfs(dfs, 0); // 从第0行开始，从行开始回溯，默认每次放置的皇后都不再同一行
return ans;
}
};
题目链接：37.解数独 思路：
回溯数独每一个位置，每个位置需要填写时，从1-9选择一个数； 每个数的填充需要进行判断是否符合数独的条件。 代码： class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
int n = board.size();
// 判断当前位置是否符合数独条件
auto isTrue = [&] (int row, int col, char val) {
for (int i = 0; i < 9; i++) { // 判断行里是否重复
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) { // 判断列里是否重复
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
};
auto dfs = [&](auto&& dfs) -> bool {
// 遍历数独
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(board[i][j] != '.')
continue;
// 需要填充时，从1到9选择
for(int k = 1; k <= 9; k++) {
if(isTrue(i, j, k + '0')) { // 判断当前位置放入 k ,是否符合数独条件
board[i][j] = k + '0';
if(dfs(dfs))
return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
};
dfs(dfs);
}
};
![HTB：Sightless[WriteUP]](https://i-blog.csdnimg.cn/direct/ebdaea9ce07c45c1b401e4616ee0c723.png)
