回溯跟枚举差不多。要注意“回溯”，别忘记“回”之前把之前的改动都复原。

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-9
        for (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;
    }
};