回溯跟枚舉差不多。要注意“回溯”，別忘記“回”之前把之前的改動都復原。

leetcode37

leetcode37是解數獨問題。本題保證有且僅有唯一解。

思路：先把空格子的位置存下來，然后對每一個空位置挨個枚舉1-9。枚舉之前，先建立一個一維數組，把要排除的數先排除，效率會高些。

class Solution {// 空格的信息int x[100], y[100], cnt = 0;bool dfs(int i, vector<vector<char>>& board) {if (i == cnt) return true;bool s[60] = {false};// 檢查行、列for (int j = 0; j < 9; j++) s[board[x[i]][j]] = s[board[j][y[i]]] = true;// 檢查九宮格for (int j = x[i] / 3 * 3; j < x[i] / 3 * 3 + 3; j++)for (int k = y[i] / 3 * 3; k < y[i] / 3 * 3 + 3; k++)s[board[j][k]] = true;// 枚舉嘗試1-9for (char c = '1'; c <= '9'; c++) {if (s[c] == false) {board[x[i]][y[i]] = c;if (dfs(i + 1, board))return true;}}board[x[i]][y[i]] = '.';return false;}public:void solveSudoku(vector<vector<char>>& board) {// 檢索空格子for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {x[cnt] = i;y[cnt++] = j;}}}dfs(0, board);return;}
};

leetcode17

leetcode17是純純的枚舉問題。

逐位處理那串數字，把記錄好的當作參數string alreadyHave。由于這個形參是每遞歸一下就新開辟一個棧幀，所以這樣寫不涉及到“改動復原”的事。如果占用空間太大了，就需要把這個參數改為引用，那么就需要“復原”了。

class Solution {vector<string> ans;string d;void dfs(int index, string alreadyHave) // index是待處理下標{if (index == d.length()) {if (alreadyHave != "")ans.push_back(alreadyHave);return;}int num = d[index] - '0', start, end;if (num >= 2 && num <= 7) {start = (num - 2) * 3 + 'a';end = start + 2;}if (num == 7)end++;if (num == 8) {start = 't';end = 'v';}if (num == 9) {start = 'w';end = 'z';}for (int i = start; i <= end; i++) {dfs(index + 1, alreadyHave + (char)(i));}return;}public:vector<string> letterCombinations(string digits) {d = digits;dfs(0, "");return ans;}
};