目录：
- 二叉树回溯
- 257. 二叉树的所有路径
- 组合问题
- 77. 组合
- 216. 组合总和 III
- 17. 电话号码的字母组合
- 39. 组合总和
- 40. 组合总和 II
- 分割问题
- 131. 分割回文串
- 93. 复原 IP 地址
- 子集问题
- 78. 子集
- 90. 子集 II
- 排列问题
- 46. 全排列
- 47. 全排列 II
- 棋盘问题
- 51. N 皇后
- 37. 解数独
- 其他问题
- 332. 重新安排行程
- 491. 递增子序列
\quad
\quad
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯法并不是什么高效的算法，因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的 *** 作，但也改不了回溯法就是穷举的本质。
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
什么是组合，什么是排列？
- 组合不强调元素顺序，排列强调元素顺序。
回溯法解决的问题都可以抽象为树形结构！因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度构成的树的深度。只要是递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。
回溯法模板回溯三部曲：
- 回溯函数模板返回值以及参数
- 回溯算法中函数返回值一般为void。
- 因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
void backtracking(参数)
- 回溯函数终止条件
- 什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
if (终止条件) {
存放结果;
return;
}
- 回溯搜索的遍历过程
回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking实现递归。
for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历。
这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
回溯算法模板框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
给你一个二叉树的根节点 root ，按任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (!root) return result;
traversal(root, path, result);
return result;
}
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.push_back(cur->val); // 中
if (cur->left == nullptr && cur->right == nullptr) {
string sPath;
for (int i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]);
result.push_back(sPath);
return;
}
if (cur->left) {
traversal(cur->left, path, result);
path.pop_back();
}
if (cur->right) {
traversal(cur->right, path, result);
path.pop_back();
}
}
};
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (!root) return result;
traversal(root, path, result);
return result;
}
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); //中
if (cur->left == nullptr && cur->right == nullptr) {
result.push_back(path);
return;
}
if (cur->left) {
traversal(cur->left, path + "->", result);
}
if (cur->right) {
traversal(cur->right, path + "->", result);
}
}
};
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
如果要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，回溯法就用递归来解决嵌套层数的问题。
递归来做层叠嵌套，每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。
思路：
- 从左往右取数，取过的数不再重复取
- 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
- 可以发现n相当于树的宽度，k相当于树的深度。
- 每次搜索到了叶子节点，我们就找到了一个结果。
只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
{
public:
vector<int> path;
vector<vector<int>> result;
public:
vector<vector<int>> combine(int n, int k)
{
path.clear();
result.clear();
backtracking(n, k, 1); // 思考下为啥为1
return result;
}
void backtracking(int n, int k, int startIndex)
{
if (path.size() == k)
{
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) // 控制树的横向遍历
{
path.push_back(i);
backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
path.pop_back();
}
}
};
剪枝：
可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
可以看一下n=4,k=4的情况。
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= (n - (k - path.size()) + 1); i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
path.clear();
result.clear();
backtracking(k, n, 0, 1);
return result;
}
void backtracking(int k, int n, int sum, int startIndex) {
if (path.size() == k) {
if (sum == n) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9; i++) {
sum += i;
path.push_back(i);
backtracking(k, n, sum, i + 1);
path.pop_back();
sum -= i;
}
}
private:
vector<vector<int>> result;
vector<int> path;
};
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
path.clear();
result.clear();
backtracking(k, n, 0, 1);
return result;
}
void backtracking(int k, int n, int sum, int startIndex) {
if (sum > n) return;
if (path.size() == k) {
if (sum == n) result.push_back(path);
return;
}
for (int i = startIndex; i <= (9 - (k - path.size()) + 1); i++) {
sum += i;
path.push_back(i);
backtracking(k, n, sum, i + 1);
path.pop_back();
sum -= i;
}
}
private:
vector<vector<int>> result;
vector<int> path;
};
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下。注意 1 不对应任何字母。
class Solution {
public:
vector<string> letterCombinations(string digits) {
s.clear();
result.clear();
if (digits.size() == 0) return result;
backtracking(digits, 0);
return result;
}
void backtracking(const string &digits, int index) {
if (digits.size() == index) {
result.push_back(s);
return;
}
int digit = digits[index] - '0';
string letters = letterMap[digit];
for (int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]);
backtracking(digits, index + 1); // 递归，注意index+1，一下层要处理下一个数字了
s.pop_back();
}
}
private:
vector<string> result;
string s;
const string letterMap[10] = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
};
class Solution {
public:
vector<string> letterCombinations(string digits) {
result.clear();
if (digits.size() == 0) return result;
backtracking(digits, 0, "");
return result;
}
void backtracking(const string &digits, int index, const string& s) {
if (digits.size() == index) {
result.push_back(s);
return;
}
int digit = digits[index] - '0';
string letters = letterMap[digit];
for (int i = 0; i < letters.size(); i++) {
backtracking(digits, index + 1, s + letters[i]); // 递归，下一层处理下一个数字
}
}
private:
vector<string> result;
const string letterMap[10] = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
};
\quad
\quad
用startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
- 如果是一个集合来求组合的话，就需要startIndex；
- 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex。
\quad
\quad
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
class Solution {
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
result.clear();
path.clear();
backtracking(candidates, target, 0, 0);
return result;
}
void backtracking(vector<int> &candidates, int target, int sum, int startIndex) {
if (sum > target) return;
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
path.pop_back();
sum -= candidates[i];
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
剪枝优化：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end()); // 需要排序
backtracking(candidates, target, 0, 0);
return result;
}
void backtracking(vector<int> &candidates, int target, int sum, int startIndex) {
if (sum > target) return;
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
path.pop_back();
sum -= candidates[i];
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
40. 组合总和 II在求和问题中，排序之后加剪枝是常见的套路！
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
这道题目和39. 组合总和如下区别：
- 本题candidates 中的每个数字在每个组合中只能使用一次。
- 本题数组candidates的元素是有重复的，而39. 组合总和是无重复元素的数组candidates。
本题的难点在于集合中有重复元素，但还不能有重复的组合。
- 如果把所有组合求出来，再用set或者map去重，这可以，但是很容易超时！所以要在搜索的过程中就去掉重复组合。
- 所谓去重，其实就是使用过的元素不能重复选取。 组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。
- 元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
如果树层去重的话，需要对数组排序！
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
vector<bool> used(candidates.size(), false);
path.clear();
result.clear();
sort(candidates.begin(), candidates.end()); // 首先把给candidates排序，让其相同的元素都挨在一起。
backtracking(candidates, target, 0, 0, used);
return result;
}
void backtracking(vector<int> &candidates, int target, int sum, int startIndex, vector<bool> &used) {
if (sum > target) return;
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
sum += candidates[i];
used[i] = true;
path.push_back(candidates[i]);
// 这里是i+1，每个数字在每个组合中只能使用一次
backtracking(candidates, target, sum, i + 1, used);
path.pop_back();
used[i] = false;
sum -= candidates[i];
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
在candidates[i] == candidates[i - 1]相同的情况下：
- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
- used[i - 1] == false，说明同一树层candidates[i - 1]使用过
直接使用startIndex去重。
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
vector<bool> used(candidates.size(), false);
path.clear();
result.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0);
return result;
}
void backtracking(vector<int> &candidates, int target, int sum, int startIndex) {
if (sum > target) return;
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
if (i > startIndex && candidates[i - 1] == candidates[i]) continue;
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1);
path.pop_back();
sum -= candidates[i];
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
切割问题类似组合问题。例如对于字符串abcdef：
- 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…
- 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…
class Solution {
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
void backtracking(string &s, int startIndex) {
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome(s, startIndex, i)) {
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else {
continue;
}
backtracking(s, i + 1);
path.pop_back();
}
}
static bool isPalindrome(const string &s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) return false;
}
return true;
}
private:
vector<string> path;
vector<vector<string>> result;
};
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
- 例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
backtracking(s, 0, 0);
return result;
}
void backtracking(string &s, int startIndex, int pointNum) {
if (pointNum == 3) {
if (isValid(s, startIndex, s.size() - 1)) {
result.push_back(s);
}
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isValid(s, startIndex, i)) {
s.insert(s.begin() + i + 1, '.');
pointNum++;
backtracking(s, i + 2, pointNum);
pointNum--;
s.erase(s.begin() + i + 1);
}
}
}
// 段位以0为开头的数字不合法 段位里有非正整数字符不合法 段位如果大于255了不合法
static bool isValid(string &s, int start, int end) {
if (start > end) return false;
if (s[start] == '0' && start != end) return false;
string str = s.substr(start, end - start + 1);
int num = atoi(str.c_str());
if (num > 255 || num < 0) {
return false;
}
return true;
}
private:
vector<string> result;
};
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
class Solution {
public:
vector<vector<int>> subsets(vector<int> &nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
void backtracking(vector<int> &nums, int startIndex) {
result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
使用used数组去重：
class Solution2 {
public:
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(nums, 0, used);
return result;
}
void backtracking(vector<int> &nums, int startIndex, vector<bool> &used) {
result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
for (int i = startIndex; i < nums.size(); i++) {
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
if (i > 0 && nums[i] == nums[i - 1] && used[i-1] == false) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
private:
vector<int> path;
vector<vector<int>> result;
}
使用startIndex去重：
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end());
backtracking(nums, 0);
return result;
}
void backtracking(vector<int> &nums, int startIndex) {
result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
for (int i = startIndex; i < nums.size(); i++) {
if (i > startIndex && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
使用set去重：
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end());
backtracking(nums, 0);
return result;
}
void backtracking(vector<int> &nums, int startIndex) {
result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
unordered_set<int> uset;
for (int i = startIndex; i < nums.size(); i++) {
if(uset.find(nums[i])!=uset.end()) continue;
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {
public:
vector<vector<int>> permute(vector<int> &nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
void backtracking(vector<int> &nums, vector<bool> used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int> &nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(nums, used);
return result;
}
void backtracking(vector<int> &nums, vector<bool> &used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used[i - 1] == true，说明同一树枝nums[i - 1]使用过
// used[i - 1] == false，说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
used[i] = false;
path.pop_back();
}
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
首先来看一下皇后的约束条件：
- 不能同行
- 不能同列
- 不能同斜线
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
vector<string> chessboard(n, string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
// n 为输入的棋盘大小 row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string> &chessboard) {
if (row == n) {
result.push_back(chessboard);
return;
}
// 棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度
for (int col = 0; col < n; col++) {
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
}
bool isValid(int row, int col, vector<string> &chessboard, int n) {
// 检查列
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 'Q') return false;
}
// 在单层搜索的过程中，每一层递归，只会选for循环里的一个元素，所以不用检查行了
// 检查45度角是否有皇后
for (int i = col - 1, j = row - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[j][i] == 'Q') return false;
}
// 检查 135度角是否有皇后
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') return false;
}
return true;
}
private:
vector<vector<string>> result;
};
编写一个程序，通过填充空格来解决数独问题。数独的解法需 遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
class Solution {
public:
void solveSudoku(vector<vector<char>> &board) {
backtracking(board);
}
bool backtracking(vector<vector<char>> &board) {
for (int i = 0; i < board.size(); i++) { // 遍历行
for (int j = 0; j < board[0].size(); j++) { // 遍历列
if (board[i][j] != '.') continue;
for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
if (isValid(i, j, k, board)) {
board[i][j] = k;
if (backtracking(board)) return true; // 如果找到合适一组立刻返回
board[i][j] = '.';
}
}
return false; // 9个数都试完了，都不行，那么就返回false
}
}
return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
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;
}
};
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
- 例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
class Solution {
public:
vector<string> findItinerary(vector<vector<string>> &tickets) {
targets.clear();
vector<string> result;
for (const vector<string> &vec: tickets) {
targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场
backtracking(tickets.size(), result);
return result;
}
// 只需要找到一个行程，所以找到了直接返回bool
bool backtracking(int tickNum, vector<string> &result) { // tickNum表示有多少个航班
if (result.size() == tickNum + 1) {
return true; // 这里的result相当于之前的path，不需要手收集结果
}
for (pair<const string, int> &target: targets[result[result.size() - 1]]) {
if (target.second > 0) { // 记录到达机场是否飞过了
result.push_back(target.first);
target.second--;
if (backtracking(tickNum, result)) return true;
result.pop_back();
target.second++;
}
}
return false;
}
private:
// unordered_map<出发机场, map<到达机场, 航班次数>>
unordered_map<string, map<string, int>> targets;
};
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int> &nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
void backtracking(vector<int> &nums, int startIndex) {
if (path.size() > 1) {
result.push_back(path);
}
unordered_set<int> uset;
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()) continue;
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int> &nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
void backtracking(vector<int> &nums, int startIndex) {
if (path.size() > 1) {
result.push_back(path);
}
int used[201] = {0};
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums[i] < path.back()) || used[nums[i] + 100] == 1) continue;
used[nums[i] + 100] = 1;
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
private:
vector<int> path;
vector<vector<int>> result;
};
\quad
\quad
\quad
以上题解大多来自【代码随想录】（完整版看这个！！），在此基础上做了一定总结，并附带一些自己的理解。
后续题目，随缘更新，有错误请指出！
END
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）