boolisValid(vector<string>& chessboard, int n, int row, int col) { // 同一列中不能有两个皇后 for (int i = 0; i < row; i ++ ) if (chessboard[i][col] == 'Q') returnfalse;
// 主对角线不能有两个皇后 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i -- , j -- ) if (chessboard[i][j] == 'Q') returnfalse;
// 副对角线不能有两个皇后 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i -- , j ++ ) if (chessboard[i][j] == 'Q') returnfalse;
returntrue; }
// 传入棋盘，棋盘大小，行数（即递归层数） voidbacktracking(vector<string>& chessboard, int n, int row) { // 终止条件 if (row == n) { res.push_back(chessboard); return; }
// 单层递归逻辑 for (int i = 0; i < n; i ++ ) { // 合法性判断 if (isValid(chessboard, n, row, i)) { // 放皇后 chessboard[row][i] = 'Q'; // 递归 backtracking(chessboard, n, row + 1); // 回溯 chessboard[row][i] = '.'; } } }
classSolution { public: boolisValid(int i, int j, char k, vector<vector<char>>& board) { // 检查第i行能否放入k for (int j = 0; j < board[0].size(); j ++ ) if (board[i][j] == k) returnfalse;
// 检查第j列能否放入k for (int i = 0; i < board.size(); i ++ ) if (board[i][j] == k) returnfalse; // 检查九宫格能否放入k int starti = i / 3 * 3; int startj = j / 3 * 3; int endi = starti + 2; int endj = startj + 2; for (int i = starti; i <= endi; i ++ ) for (int j = startj; j <= endj; j ++ ) if (board[i][j] == k) returnfalse;
returntrue; }
boolbacktracking(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] == '.') { // 处理节点 for (char k = '1'; k <= '9'; k ++ ) { if (isValid(i, j, k, board)) { board[i][j] = k; // 递归 bool res = backtracking(board); if (res == true) returntrue; // 回溯 board[i][j] = '.'; } } returnfalse; } } returntrue; }
// 左闭右闭写法 classSolution { public: // 寻找左边界 // 说明target在[left, mid]之间 intfindLeftBorder(vector<int>& nums, int target) { int leftBorder = -2; int left = 0, right = nums.size() - 1;
while (left <= right) { int mid = left + (right - left) / 2; // 在[left, mid]中更新左边界 if (nums[mid] >= target) { right = mid - 1; leftBorder = right; } else left = mid + 1; } return leftBorder; }
// 寻找右边界 // 说明target在[mid, right]之间 intfindRightBorder(vector<int>& nums, int target) { int rightBorder = -2; int left = 0, right = nums.size() - 1;
while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) right = mid - 1; // 在[mid, right]中更新右边界 else { left = mid + 1; rightBorder = left; } } return rightBorder; }
vector<int> searchRange(vector<int>& nums, int target){ int leftBorder = findLeftBorder(nums, target); int rightBorder = findRightBorder(nums, target);
// 左闭右闭写法 classSolution { public: // 寻找左边界 // 说明target在[left, mid]之间 intfindLeftBorder(vector<int>& nums, int target) { int leftBorder = -2; int left = 0, right = nums.size() - 1;
while (left <= right) { int mid = left + (right - left) / 2; // 在[left, mid]中更新左边界 if (nums[mid] >= target) { right = mid - 1; leftBorder = mid; } else left = mid + 1; } return leftBorder; }
// 寻找右边界 // 说明target在[mid, right]之间 intfindRightBorder(vector<int>& nums, int target) { int rightBorder = -2; int left = 0, right = nums.size() - 1;
while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) right = mid - 1; // 在[mid, right]中更新右边界 else { left = mid + 1; rightBorder = mid; } } return rightBorder; }
vector<int> searchRange(vector<int>& nums, int target){ int leftBorder = findLeftBorder(nums, target); int rightBorder = findRightBorder(nums, target);
classSolution { public: intminSubArrayLen(int target, vector<int>& nums){ int len = INT_MAX; int s = 0; // 滑动窗口的和 int i = 0; // 起始位置
// j为终止位置 for (int j = 0; j < nums.size(); j ++ ) { s += nums[j]; // 终止位置划入
while (s >= target) { int sub = j - i + 1; if (sub < len) len = sub; s -= nums[i]; // 起始位置从和中滑出 i ++ ; // 起始位置从滑动窗口中滑出 } } if (len == INT_MAX) return0; elsereturn len; } };
// 左闭右闭写法 classSolution { public: intsearch(vector<int>& nums, int target){ int left = 0, right = nums.size() - 1; // 本质是查找target，因此是小于等于。若是查找最小值，则是小于 while (left <= right) { int mid = left + (right - left) / 2;
// 第一种情况，直接找到 if (nums[mid] == target) return mid;
// 由于第一种情况已经讨论过nums[mid] == target，因此第二三种情况不用再讨论 // 第二种情况，数组最小值在右侧, [left, mid]为有序 if (nums[mid] > nums[right]) { // target在[left, mid](有序)内 if (target >= nums[left] && target < nums[mid]) right = mid - 1; // target在无序区间内 else left = mid + 1; }
classSolution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2){ int hash1[1010] = {0}; int hash2[1010] = {0}; vector<int> res;
for (int i = 0; i < nums1.size(); i ++ ) hash1[nums1[i]] ++ ; for (int i = 0; i < nums2.size(); i ++ ) hash2[nums2[i]] ++ ; for (int i = 0; i < 1010; i ++ ) { if (hash1[i] && hash2[i]) res.push_back(i); } return res; } };
for (int i = 0; i < nums1.size(); i ++ ) hash[nums1[i]] ++ ; for (int i = 0; i < nums2.size(); i ++ ) if (hash[nums2[i]]) res.insert(nums2[i]); returnvector<int>(res.begin(), res.end()); } };
classSolution { public: vector<int> twoSum(vector<int>& nums, int target){ unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i ++ ) { int t = target - nums[i]; if (m.find(t) != m.end()) { auto it = m.find(t); return {i, it->second}; } m.insert({nums[i], i}); } return {}; } };
classSolution { public: vector<int> twoSum(vector<int>& nums, int target){ unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i ++ ) m.insert({nums[i], i}); for (int i = 0; i < nums.size(); i ++ ) { int t = target - nums[i]; auto it = m.find(t); if (it != m.end() && it->second != i) return {i, it->second}; } return {}; } };
for (int i = 0; i < magazine.size(); i ++ ) cnt[magazine[i] - 'a'] ++ ; for (int i = 0; i < ransomNote.size(); i ++ ) cnt[ransomNote[i] - 'a'] -- ; for (int num: cnt) if (num < 0) returnfalse; returntrue; } };
for (int i = tmp.size() - 1; i >= 0; i -- ) { // 非数字的字符 if (tmp[i] < '0' || tmp[i] > '9') returnfalse; sum += (tmp[i] - '0') * d; d = d * 10; if (sum > 255) returnfalse; } returntrue; }
// startIndex为分割线，dotSum为逗点数目 voidbacktracking(string& s, int startIndex, int dotSum) { // 终止条件 if (dotSum == 3) { // 对第四段(s的最后一段)做合法性判断 if (isvalid(s, startIndex, s.size() - 1)) { res.push_back(s); } return; } // 单层搜索逻辑 // 区间[startIndex, i] for (int i = startIndex; i < s.size(); i ++ ) { // 对区间合法性进行判断 if (isvalid(s, startIndex, i)) { // 合法，则插入逗点 s.insert(s.begin() + i + 1, '.'); dotSum ++ ;
// 递归，本区间终止于i, 故下一个区间开始于i + 2 backtracking(s, i + 2, dotSum);
int num = 0; for (int i = start; i <= end; i ++ ) { // 非数字字符 if (s[i] < '0' || s[i] > '9') returnfalse; // 在0-255之间 num = num * 10 + s[i] - '0'; if (num > 255) returnfalse; } returntrue; }
voidbacktracking(vector<int>& candidates, int target, int s, int startIndex) { if (s > target) return; if (s == target) { res.push_back(path); return; }
// 剪枝操作 for (int i = startIndex; i < candidates.size() && s + candidates[i] <= target; i ++ ) { s += candidates[i]; path.push_back(candidates[i]); backtracking(candidates, target, s, i); s -= candidates[i]; path.pop_back(); } return; }
voidbacktracking(vector<int>& candidates, int target, int s, int startIndex, vector<int> used) { // 终止条件 if (s > target) return; if (s == target) { res.push_back(path); return; }
// 单层搜索逻辑 for (int i = startIndex; i < candidates.size(); i ++ ) { // 树层去重 if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) continue; // 处理节点 path.push_back(candidates[i]); used[i] = 1; s += candidates[i];
// 递归 backtracking(candidates, target, s, i + 1, used);
// 判断[start, end]是否是回文子串 boolisPalindrome(const string& s, int start, int end) { for (int i = start, j = end; i <= j; i ++ , j -- ) if (s[i] != s[j]) returnfalse; returntrue; }
voidbacktracking(const string& s, int startIndex) { // 终止条件 if (startIndex >= s.size()) { res.push_back(path); return; }
// 单层搜索逻辑 for (int i = startIndex; i < s.size(); i ++ ) { // 是回文子串，则将其加入path中 if (isPalindrome(s, startIndex, i)) path.push_back(s.substr(startIndex, i - startIndex + 1)); elsecontinue;
res 变量存储的是所有可能的分割方案。在极端情况下，如输入字符串完全由相同字符组成（例如 “aaaa”），分割方案的数量和其中每个方案的长度都可能接近$n$。但通常来说，我们只计算这个变量直接占用的空间，即指针或引用的空间，这通常也是$O(n^2)$，因为每个回文分割的保存都可能需要一个长度为 的$n$字符串的复制。
辅助空间：
检查回文所用的额外空间是常量级的，不随输入大小变化。
将以上所有考虑结合，整个算法的空间复杂度主要由存储所有分割方案的数组 res 决定。由于每个分割方案可能包含多个字符串，而每个字符串又可能需要$O(n)$的空间，因此在最坏情况下，这部分的空间复杂度为$O(n⋅k)$，其中 $k$是分割方案的数量，这在极端情况下可以达到$O(n^2)$。
voidbacktracking(int k, int n, int startIndex, int sum) { // 终止条件 if (path.size() == k && sum == n) res.push_back(path); // 单层搜索逻辑 for (int i = startIndex; i <= 9; i ++ ) { // 处理节点 sum += i; path.push_back(i); // 递归 backtracking(k, n, i + 1, sum); // 回溯 sum -= i; path.pop_back(); } } vector<vector<int>> combinationSum3(int k, int n) { backtracking(k, n, 1, 0); return res; } };
// index用于标识传入的字符串digits在当前递归中遍历到哪一个字符（实际上是数字）了 // startIndex一般用于一个集合中求组合，避免得到重复的组合 // 本题是在多个集合中各取一个元素出来做组合，因此不需要startIndex来帮助控制集合中之前遍历过哪些元素 voidbacktracking(string digits, int index) { // 终止条件 // index指向digits的最后一位的下一位，才终止。若index指向digits的最后一位，其后应该还有处理最后一位的逻辑 if (index == digits.size()) { res.push_back(s); // 收获结果 return; } // 单层搜索逻辑 // 取出digits中的数字 int digit = digits[index] - '0'; // 字符转换为数字 // 找出digit对应的字符串 string letter = letterMap[digit]; // 遍历digit对应的字符串 for (int i = 0; i < letter.size(); i ++ ) { // 处理节点 s.push_back(letter[i]); // 下一层递归，index后移一位 backtracking(digits, index + 1); // 回溯 s.pop_back(); } }
本题看似复杂，但画图理解后逻辑清晰，代码也不长。
可以将代码写得更简洁，递归函数传入三个参数：void backtracking(string digits, int index, string s)，然后单层搜索逻辑的三行代码写成一行：backtracking(digits, index + 1, s + letter[i]);。s的值本身并没有改变，这就是将回溯的过程隐藏在参数中了。
voidbacktracking(string digits, int index, string s) { if (index == digits.size()) { res.push_back(s); return; }
// 单层搜索逻辑 int digit = digits[index] - '0'; string letter = all[digit]; for (int i = 0; i < letter.size(); i ++ ) backtracking(digits, index + 1, s + letter[i]); }
结果集 result 虽然result用来存储所有可能的组合，其大小可以达到组合数$C(n, k)$，但在分析空间复杂度时，我们通常不把输出空间计算在内，因为这部分空间是用来存储算法的最终结果，而非算法执行过程中的临时数据。如果包括result的空间，空间复杂度确实是$O(C(n, k))$，但这不是额外的空间，而是算法结果的必要空间。
