3. 子集问题
要清楚子集问题和组合问题、分割问题的的区别，子集是收集树形结构中树的所有节点的结果。
而组合问题、分割问题是收集树形结构中叶子节点的结果。
78. 子集【中等】
class Solution { private: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { res.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己 //if (startIndex >= nums.size()) { // 终止条件可以不加 // return; //} for (int i = startIndex; i < nums.size(); i++) { path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); } return; } public: vector<vector<int>> subsets(vector<int>& nums) { backtracking(nums, 0); return res; } };
90. 子集 II【中等】
题目意思：多了去重
- 思路一
class Solution { private: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { res.push_back(path); for (int i = startIndex; i < nums.size(); i++) { // 而我们要对同一树层使用过的元素进行跳过 if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex continue; } path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); // 去重需要排序 backtracking(nums, 0); return res; } };
思路二：使用set去重
class Solution { private: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { res.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(); } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); // 去重需要排序 backtracking(nums, 0); return res; } };
思路三：used数组去重
class Solution { private: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) { res.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; } path.push_back(nums[i]); used[i] = true; backtracking(nums, i + 1, used); used[i] = false; path.pop_back(); } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<bool> used(nums.size(), false); //used数组初始化 sort(nums.begin(), nums.end()); // 去重需要排序 backtracking(nums, 0, used); return res; } };
491. 递增子序列【中等】
- [x]
class Solution { private: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { if (path.size() >= 2) res.push_back(path); unordered_set<int> uset; // 使用set对本层元素进行去重 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(); } return; } public: vector<vector<int>> findSubsequences(vector<int>& nums) { backtracking(nums, 0); return res; } };
优化：数组替代哈希表
注意题目中说了，数值范围[-100,100]，所以完全可以用数组来做哈希
程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且每次重新定义set，insert的时候其底层的符号表也要做相应的扩充，也是费事的。
class Solution { private: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { if (path.size() > 1) res.push_back(path); int used[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100] 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(); } } public: vector<vector<int>> findSubsequences(vector<int>& nums) { backtracking(nums, 0); return res; } };
4. 全排列
46. 全排列【中等】
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used) { // 此时说明找到了一组 if (path.size() == nums.size()) { res.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; // path里已经收录的元素，直接跳过 used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } return; } vector<vector<int>> permute(vector<int>& nums) { vector<bool> used(nums.size(), false); backtracking(nums, used); return res; } };
47. 全排列 II【中等】
class Solution { private: vector<vector<int>> res; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used) { // 此时说明找到了一组 if (path.size() == nums.size()) { res.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] == nums[i - 1] && used[i - 1] == false) { continue; } //去重 if (used[i] == false) { used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); // 排序 vector<bool> used(nums.size(), false); backtracking(nums, used); return res; } };
5. 棋盘问题
51. N 皇后【困难】
规则：
- 不能同行
- 不能同列
- 不能同斜线 （45度和135度角）
class Solution { private: vector<vector<string>> res; // n 为输入的棋盘大小 // row 是当前递归到棋盘的第几行了 void backtracking(int n, int row, vector<string>& chessboard) { //收集答案 if (row == n) { result.push_back(chessboard); return; } 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) { int count = 0; // 检查列 for (int i = 0; i < row; i++) { // 这是一个剪枝 if (chessboard[i][col] == 'Q') { return false; } } // 检查 45度角是否有皇后 for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) { if (chessboard[i][j] == '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; } public: vector<vector<string>> solveNQueens(int n) { vector<string> chessboard(n, string(n, '.')); backtracking(n, 0, chessboard); return res; } };
37. 解数独【困难】
题目意思：解数独，唯一解，且都是9*9数独
规则：
- 同行不能重复
- 同列不能重复
- 3*3不能重复
class Solution { private: 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; // 放置k if (backtracking(board)) return true; // 如果找到合适一组立刻返回 board[i][j] = '.'; // 回溯，撤销k } } 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; } public: void solveSudoku(vector<vector<char>>& board) { backtracking(board); } };
6. 其他
332. 重新安排行程【困难】
题目意思：所有机票必须用一次且只能用一次
class Solution { private: // unordered_map<出发机场, map<到达机场, 航班次数>> targets unordered_map<string, map<string, int>> targets; bool backtracking(int ticketNum, vector<string>& res) { if (res.size() == ticketNum + 1) return true; //机票都用了一次 for (pair<const string, int>& target : targets[res[res.size() - 1]]) { if (target.second > 0 ) { // 记录到达机场是否飞过了 res.push_back(target.first); target.second--; if (backtracking(ticketNum, res)) return true; res.pop_back(); target.second++; } } return false; } public: vector<string> findItinerary(vector<vector<string>>& tickets) { vector<string> res; for (const vector<string>& vec : tickets) { //遍历机票 targets[vec[0]][vec[1]]++; // 记录映射关系 } res.push_back("JFK"); // 起始机场 backtracking(tickets.size(), res); return res; } };
性能分析
关于回溯算法的复杂度分析在网上的资料鱼龙混杂，一些所谓的经典面试书籍不讲回溯算法，算法书籍对这块也避而不谈，感觉就像是算法里模糊的边界。
以下在计算空间复杂度的时候我都把系统栈（不是数据结构里的栈）所占空间算进去。
子集问题分析：
- 时间复杂度O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为O(2^n)
- 空间复杂度： O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n)
排列问题分析：
- 时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * … 1 = n!。
- 空间复杂度：O(n)，和子集问题同理。
组合问题分析：
- 时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
- 空间复杂度：O(n)，和子集问题同理。
N皇后问题分析：
- 时间复杂度：O(n!)，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n * (n-1) * … * 1。
- 空间复杂度：O(n)，和子集问题同理。
解数独问题分析：
- 时间复杂度：O(9^m), m是’.'的数目。
- 空间复杂度：O(n^2)，递归的深度是n^2
