总言

  主要内容：编程题举例，熟悉理解回溯剪枝类题型（如何画决策树，如何使用深搜进行递归，如何运用剪枝，如何在一维数组/二维数组中使用）。

  
  
  
  
  
  
  
  

1、回溯和剪枝

  回溯和剪枝是在算法设计中常用的两个概念。通常用于解决组合问题、排列问题和搜索问题等（尤其在搜索算法，如深度优先搜索（DFS）和广度优先搜索（BFS）中）。

  回溯（Backtracking）： 回溯算法，又称为“试探法”，是一种通过搜索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些更改来丢弃该解，即“回溯”并尝试另一个可能的解。
  简单来说，回溯算法是一种走不通就回退再走的方法。它在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。该算法通常与递归结合使用，因为递归允许算法在到达某个点后“回溯”到之前的状态。
  
  
  剪枝（Pruning）： 剪枝是一种优化策略，用于减少搜索算法中的不必要计算。 在搜索过程中，剪枝可以识别并丢弃那些不可能导致有效解的路径，从而节省计算资源。
  在回溯算法中，剪枝通常通过预先定义的规则或条件来实现，这些规则或条件用于判断当前搜索路径是否可能导致有效解。如果不可能，则算法会停止在当前路径上的进一步搜索，并回溯到上一个节点尝试其他路径。
  剪枝可以显著提高回溯算法的效率，因为它避免了不必要的计算。然而，剪枝规则的设计需要仔细考虑，以确保算法的正确性和完整性。
  
  
  
  
  
  
  
  

2、全排列（medium）

  题源：链接。

  
  

2.1、题解

  1）、思路分析
  主要在于穷举出所有排列情况，若数组元素个数较少，比如num.size()==3，那么完全可以三层循环搞定。但对于num.size()很大的情况下，循环层数会过多，因此，相对来说选择递归的方式比较合适。
  
  此类题型属于回溯题目，需要在每⼀个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式，不断地枚举每个数在当前位置的可能性，并回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。
  因此整个流程即：想一种能够满足题目要求的解题策略→获取决策树→将其设计成代码。（至于什么样的决策，什么样的树，这个形式可多种，只要能解题即可。）
  

  
  2）、题解

class Solution {
    vector<vector<int>> ret; // 用于记录整体返回结果
    vector<int> path;        // 用于记录单条路径结果
    bool visited[7]; // 用于记录元素是否遍历：提示给定数组num不超过6个

public:
    vector<vector<int>> permute(vector<int>& nums) {
        DFS(nums);
        return ret;
    }

    void DFS(vector<int>& nums) {
        // 递归结束条件：遍历到决策树的叶子节点（单次全排列元素均列举完成）
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return;
        }

        // 前序遍历：先处理当前层，再递归进入下层
        // 选择添加进入路径中的元素
        for (int i = 0; i < nums.size(); ++i) {
            if (!visited[i]) // 当前元素下标为false，表示该元素在当前路径中未被排列，可用
            {
                path.push_back(nums[i]);
                visited[i] = true;

                // 继续向下层递归
                DFS(nums);

                // 回溯：来到这里，说明已经递归回到当前层，需要恢复现现场(注意这里需要处理的数据有哪些）
                // 选择在此处回溯而非递归结束条件处，是因为递归的每一层返回，都需要恢复一次现场，统一在此处处理，就不用写两遍了。
                path.pop_back();
                visited[i] = false;
            }
        }
    }
};

  
  
  
  
  
  
  
  

3、子集（medium）

  题源：链接。

  

3.1、题解

  解法一： 遍历数组，对数组中的每个元素进⾏选择或不选择的操作，获取决策树。

class Solution {
    vector<vector<int>> ret; // 用于返回所有子集
    vector<int> path;        // 某一单一子集的情况
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        DFS(nums,0);//这里pos是数组下标
        return ret;
    }

    void DFS(vector<int>& nums, int pos)
    {
    	// 递归结束条件
        if(pos == nums.size())
        {
            ret.push_back(path);
            return;
        }
        
        // 从pos位置选数：两种情况，选pos，不选pos
        // 不选的情况：
        DFS(nums, pos+1);//更新pos位置，继续向下一层递归
        //此处不需要恢复现场(没有对当前元素做选择)

        // 选择的情况：
        path.push_back(nums[pos]);// 选择当前pos位置的元素添入路径中，继续后续递归
        DFS(nums, pos+1);
        path.pop_back();//因为选择了pos位置的元素，递归返回上一层时需要回溯（恢复现场）

    }
};

  
  
  解法二： 按照元素个数为0个、1个、2个、……、n个的顺序，获取决策树。

class Solution {
    vector<vector<int>> ret;// 用于返回所有子集
    vector<int> path;// 某一单一子集的情况

public:
    vector<vector<int>> subsets(vector<int>& nums) {
         DFS(nums, 0);
         return ret;
    }

    void DFS(vector<int>& nums, int pos)
    {
        // 前序
        // 先将当前path中的子集添加入幂集中（为了统一，方便处理空集）
        ret.push_back(path);

        // 递归结束条件：该层已经无情况
        // 注意：由于这里我们在遍历到下一层时，才将上一层获取的子集存入幂集中，因此，这里要递归结束前要先push上一次结果。
        // 其它：这里不加这个if判断也行，因为下述for循环在i = nums.size() - 1时会再此递归，即第nums.size()次，不满足条件结束递归。
        if(pos == nums.size())
        {
            return;
        }

        // 从给定的pos位置开始选数
        for(int i = pos; i < nums.size(); ++i)
        {
            // 当前层：选择比上层多一个数
            path.push_back(nums[i]);
            // 进入下一层：从当前位置的下一个位置开始选数
            DFS(nums, i + 1);
            // 来到此处，递归结束返回当前层，需要回溯（恢复现场）
            path.pop_back();
            // 继续遍历，寻找其它情况
        }
    }
    };

  
  
  
  
  
  
  
  

4、找出所有子集的异或总和再求和（easy）

  题源：链接。

  
  

4.1、题解

  说明：此题解法策略和上题求子集相同，只是加入了异或处理。

class Solution {
    int total = 0;
    vector<int> path;
public:
    int subsetXORSum(vector<int>& nums) {
        DFS(nums, 0);
        return total;
    }

    void DFS(vector<int>& nums,int pos)
    {
        //处理上层结果：异或和
        int ret = 0;
        for(auto n : path)
        {
            ret^=n;
        }
        total+=ret;

        for(int i = pos; i < nums.size(); ++i)
        {
            // 当前层
            path.push_back(nums[i]);
            // 递归到下层
            DFS(nums, i + 1);
            // 回溯：恢复现场
            path.pop_back();
        }
    }
};

  对此还可以优化处理：path直接记录当前递归层的异或和。恢复现场时，只需要使用异或的性质即可：异或相同为0，path ^= nums[i];异或一遍获取该数，再异或一遍将数抵消，因此可以恢复path原值。

class Solution {
    int total = 0;    // 记录最终返回结果
    int path; // 记录决策树单条路径异或结果

public:
    int subsetXORSum(vector<int>& nums) {
        DFS(nums, 0);
        return total;
    }
    void DFS(vector<int>& nums, int pos) {
        // 处理上层结果：异或和
        total += path;

        for (int i = pos; i < nums.size(); ++i) {
            // 当前层
            path ^= nums[i];
            // 递归到下层
            DFS(nums, i + 1);
            // 回溯：恢复现场
            path ^= nums[i];
        }

};

  
  
  
  
  
  

5、全排列 Ⅱ（medium）

  题源：链接。

  

5.1、题解

  1）、思路分析
  根据题目，本题的关键点在于如何剪枝。

  这里可以从两个角度思考：
  1、只关心不合法的分支：当该条件满足时，表示其不能继续递归。

visited[i] == true || (i != 0 && num[i] == num[i-1] && num[i-1] == false)

  
  2、只关心合法的分支

visitd[i] == false && ( i == 0 || num[i] != num[i-1] || num[i-1] == true)

  visitd[i] == false：当前位置元素在一次排序回合中没有被选择过；
  num[i] != num[i-1]：当前位置元素和之前的元素不相同。
  num[i] != num[i-1] || num[i-1] == true：由于这里写的顺序， 来到num[i-1] == true判断条件处，默认num[i] == num[i-1]，前后两元素相同，此时只有二者是不同层时才合法。
  
  2）、题解

class Solution {
    bool visited[9] = {false};
    vector<int> path;// 单条路径结果
    vector<vector<int>> ret;//总路径结果
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        DFS(nums);
        return ret;
    }

    void DFS(vector<int>& nums)
    {
        if(path.size() == nums.size()) 
        {
            ret.push_back(path);//单次排序递归结束
            return;
        }

        for(int i = 0; i < nums.size(); ++i)
        {
            // 以合法可以继续往下层递归的视角
            if(visited[i] == false && (i == 0 || nums[i] != nums[i-1] || visited[i-1] == true))
            {
                path.push_back(nums[i]);
                visited[i] = true;
                DFS(nums);//递归
                visited[i] = false;//回溯：恢复现场
                path.pop_back();
            }
        }
    }
};

  
  
  
  
  

6、电话号码的字母组合（medium）

  题源：链接。

  
  

6.1、题解

  1）、思路分析
  可以使用一个字符数组nums，记录 2~9 数字各自对应的字符串(哈希映射)。遍历给定的字符串digits，提取出数字（字符数组nums的下标），即可获取到该下标处的字符串。
  然后，就是字符串的组合问题。

  2）、题解

class Solution {
    string nums[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> ret;// 记录返回结果
    string path;// 记录单条路径 
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return ret;
        DFS(digits, 0);
        return ret;
    }

    void DFS(string& digits, int pos)
    {
        // 递归结束：单条路径找到结果
        if(pos >= digits.size())
        {
            ret.push_back(path);
            return;
        }

        // 当前递归层：从pos位置开始找string中的元素
        string str = nums[digits[pos]-'0'];//  获取到对应数字隐射的字符串
        for(int i = 0; i < str.size(); ++i)// 遍历字符串选字符
        {
            // 选择当前路径字符
            path += str[i];
            // 向下层递归继续选字符
            DFS(digits, pos + 1);
            // 回到当前层：需要恢复现场
            path.pop_back();
        }
    }

};

  
  
  
  
  
  

7、括号生成（medium）

  题源：链接。

  
  

7.1、题解

  1）、思路分析
  关于此题，首先要理解有效括号，⼀种判断括号是否合法的⽅法：①从头开始的任意一个子串，从左往右遍历的过程中，左括号的数量始终大于等于右括号的数量，并且②遍历结束时，左括号的总数量与右括号的总数量相等。
  
  在此题中，对于决策树的各路分支的选择，无非就是对当前路径选左括号还是右括号。因此递归时需要进行以下判断：
  1、若选择左括号，需判断此时左括号是否超过给定的数量。
  2、若选择右括号，由于这是在遍历过程中，此时有：左括号数量 > 右括号。当左括号数量 == 右括号数量时，不能再选择右括号（因为本次的选择会造成括号不合法。）
  
  如何判断递归结束？看右括号的数量是否超过限制值。
  为什么不判断左括号？在递归过程中，左括号可以先达到最大值，（例如n=3，(((是合法的），只是意味着后续只剩下右括号可以选择。
  

  根据上图，需要两个变量分别记录左右括号在单条路径中的使用数目。此外，还需要记录单条路径和总路径情况。
  
  2）、题解

class Solution {
    string path;        // 单条路径
    vector<string> ret; // 总路径
    int left = 0;       // 单条路径中，左括号数目
    int right = 0;      // 单条路径中，右括号数目
public:
    vector<string> generateParenthesis(int n) {
        DFS(n);
        return ret;
    }

    void DFS(int& n) {
        // 递归结束条件：
        if (right == n) {
            ret.push_back(path);
            return;
        }

        // 当前层：选择左括号
        if (left < n) 
        {
            path += '(';
            ++left;

            // 继续下一层递归
            DFS(n);

            // 回溯：需要恢复现场
            path.pop_back();
            --left;
        }

        // 当前层：选择右括号
        if (left > right) 
        {
            path += ')';
            ++right;

            // 继续递归下一层
            DFS(n);

            // 回溯：需要恢复现场
            path.pop_back();
            --right;
        }
    }
};

  
  
  
  
  
  
  

8、组合（medium）

  题源：链接。

  
  

8.1、题解

  1）、思路分析
  题目要求从 1 到 n 中选择 k 个数的所有组合，其中不考虑顺序，也就是说，[1,2] 和 [2,1] 等价。我们需要找出所有的组合，但不能重复计算相同元素的不同顺序的组合。对此： ①可以将所有元素分别作为首位元素进行决策；②为避免计算重复组合，规定选择之后位置的元素时，必须比前一个元素大，这样就不会有重复的组合（[1,2] 和 [2,1] 中 [2,1] 不会出现）。

  
  2）、题解

class Solution {
    vector<vector<int>> ret;// 记录总路径结果
    vector<int> path;// 记录单条路径
public:
    vector<vector<int>> combine(int n, int k) {
        DFS(n,k,1);
        return ret;
    }

    void DFS(int& n, int& k, int pos)
    {
        // 递归结束条件：选出了n个数
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }

        // 从pos位置开始
        for(int i = pos; i <= n; ++i)
        {   // 选数
            path.push_back(i);
            // 向下一层递归
            DFS(n,k, i+1);
            // 回到当前层，恢复现场
            path.pop_back();
        }

    }
};

  
  
  
  
  
  
  

9、目标和（medium）

  题源：链接。

  
  

9.1、题解

  1）、思路分析
  对于每个数，可以选择加上或减去它，依次枚举每⼀个数字，在每个数都被选择时检查得到的和是否等于目标值。如果等于，则记录结果。
  

  这里，我们也需要记录单条路径的求值结果，我们可以将该变量path设置为递归的参数，也可以将其设置为类中变量求解。二者只是在递归时有些细节处理的区别（如，设置为类中全局变量，需要回溯；设置为传值传参，无需处理path）。
  通常，如果是简单的内置类型，比较推荐使用参数形式传递；如果是STL等复杂容器，比较推荐设置为类成员变量。（当然，这里的设置非固定，按照风格能写出代码即可。）

  2）、题解
  path记录单条路径的变量作为类成员(类中全局变量)传入。此写法下需要进行回溯。

class Solution {

public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int count = 0; // 用于记录最终获取的target数目
        int path = 0;  // 用于记录单条路径的运算结果
        DFS(nums, target, 0, path, count);
        return count;
    }

    void DFS(vector<int>& nums, int& target, int pos, int path, int& count) {
        // 递归结束条件：
        if (pos == nums.size()) {
            if (path == target)
                ++count;
            return;
        }

        // 选择 +
        path += nums[pos];
        DFS(nums, target, pos + 1, path, count);
        path -= nums[pos]; // 回溯：恢复现场（将加上的数字减去，继续其它分支选项）

        // 选择 -
        path -= nums[pos];
        DFS(nums, target, pos + 1, path, count);
        path += nums[pos]; // 回溯：恢复现场
    }
};

  
  path记录单条路径的变量作为参数传入。此写法下回溯时无需恢复现场。

class Solution {
    int count = 0; // 用于记录最终获取的target数目
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        
        int path = 0;  // 用于记录单条路径的运算结果
        DFS(nums, target, 0, path);
        return count;
    }

    void DFS(vector<int>& nums, int& target, int pos, int path) {
        // 递归结束条件：
        if (pos == nums.size()) {
            if (path == target)
                ++count;
            return;
        }

        // 选择 +
        DFS(nums, target, pos + 1, path + nums[pos]);

        // 选择 -
        DFS(nums, target, pos + 1, path - nums[pos]);
    }
};

  
  
  
  
  
  
  

10、组合总和（medium）

  题源：链接。

  
  

10.1、题解

  1）、思路分析
  注意理解题目含义：candidates 中的同一个数字可以无限制重复被选取。 根据测试用例，candidates = [2,3,5], target = 8 选出的组合[2,2,2,2]可知，这意味在决策树中，当前位置的元素可以重复被选择。

  
  2）、题解

class Solution {
    vector<vector<int>> ret;// 用于记录最终返回的组合结果
    vector<int> path;// 用于记录单条路径
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int sum = 0;
        DFS(candidates, target, 0, sum);
        return ret;
    }

    // pos记录当前递归层选数的起始位置；sum用于记录当前递归层路径和。
    void DFS(vector<int>& candidates, int target, int pos, int sum)
    {
        // 递归结束条件
        if(sum >= target)
        {
            if(sum == target)
                ret.push_back(path);
            return;
        }

        // 从给定的pos位置开始选数
        for(int i = pos; i < candidates.size(); ++i)
        {
            // 选数加入当前路径，求和
            path.push_back(candidates[i]);
            // 向下层递归
            DFS(candidates, target, i, sum + candidates[i]);
            // 递归回到当前层，回溯处理
            path.pop_back();
        }

    }
};

  
  
  
  
  
  
  
  

11、字母大小写全排列（medium）

  题源：链接。

  
  

11.1、题解

  1）、思路分析
  对给定的字符串，遍历每一个元素。
  1、若当前元素非英文字母，不进行处理，继续向后遍历；
  2、 若当前元素是英⽂字母，可以选择转换大小写，或者不转换继续向后遍历。

  
  2）、题解
  这里递归函数的写法多变，可根据自己的风格来。void DFS(string s, int pos)，在这里我们没有用引用传参，而是使用了传值传参。

class Solution {
    vector<string> ret;// 用于返回最终结果
public:
    vector<string> letterCasePermutation(string s) {
        DFS(s, 0);
        return ret;
    }

    void DFS(string s, int pos)
    {
        // 递归结束条件
        if(pos == s.size()) 
        {
            ret.push_back(s);
            return;
        }

        // 判断当前pos位置的字符是否为字母
        if(isalpha(s[pos]))
        {
            //表明当前pos位置的字符是字母

            // 选项一：不转变大小写
            //(这里先递归不转变的，再递归转变的，可以省去当前递归层的恢复现场，而对于上下递归层，由于传值传参，无需恢复现场)
            DFS(s, pos + 1);

            // 选项二：转变大小写
            if(islower(s[pos]))
                s[pos] = toupper(s[pos]);
            else s[pos] = tolower(s[pos]);
            DFS(s, pos + 1);
            
        }
        else //若当前pos位置非字母，则往后继续遍历找新字符。
            DFS(s, pos + 1);
    }
};

  
  
  
  
  
  
  

12、优美的排列（medium）

  题源：链接。

  
  

12.1、题解

  1）、思路分析
  根据题目，对给定的[1,n]范围内的数，选数进行排列，注意已经选择的数，在后续中不能重复使用。 根据返回要求，①可定义一个变量用来记录所有可能的排列数量，②一个一维数组 visited 用于标记元素。③通过深度优先搜索的方式，不断枚举每个数在当前位置的可能性，并回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。

  2）、题解

class Solution {
    int count = 0;// 统计总数
    bool visited[16];// 单条路径递归，用于判断元素是否被使用
public:
    int countArrangement(int n) {
        DFS(n, 1);
        return count;
    }

    void DFS(int n, int pos)
    {
        // 递归结束条件
        if(pos > n)
        {   
            ++count;//成功选完一条路径
            return;
        }
        // 从pos位置开始，数组第pos个位置处的元素：遍历1~n选数
        for(int i = 1; i <= n; ++i)
        {
            if(!visited[i] && (i % pos == 0 || pos % i == 0))
            {   // 当前元素未被选择，且当前元素可以构成优美数
            
                // 标记当前元素
                visited[i] = true;
                // 递归下一层继续选数
                DFS(n, pos + 1);
                // 回溯:复原现场
                visited[i] = false;
            }
        }
    }
};

  
  
  
  
  
  
  

13、N 皇后（hard）

  从本题开始就是暴搜/回溯在二维数组中的应用。注意理解学习这些方法。

  题源：链接。

  
  

13.1、题解

  1）、思路分析

  整体思路是穷举所有能够放置的合法位置。n皇后要求在(i,j)位置放置后，当前行、列、主对角线、副对角线均不冲突。这里可以从单个元素位置（i,j）的视角来考虑此题，也可以从一行的视角考虑。

  这里我们选择以每一行的视角进行考虑。 从第0行到第n行，在每一个放置一个皇后棋，因此，可以省去对行的检查（因为我们是从行的角度考虑的），此时只需要保证该皇后棋在一行中放置的位置，不会形成列冲突、对角线冲突即可。

  在检查皇后是否冲突时，①对于列，我们并不关心皇后棋出现在哪一行，只要保证所有皇后棋放置后所在的列不存在冲突即可。因此，可以用一个数组bool Col[10]来记录每⼀列已经放置的皇后棋，那么当前第i行放置时，只需要检查此时的第Col[j]列是否已经被放置过棋子即可。

  对于对角线，可以用一个数组bool Dig1[20];来标记主对角线（左上角到右下角）的每⼀条对角线上是否已经放置了皇后。同理，也用一个数组bool Dig2[20];标记副对角线（右上角到左下角）的每⼀条对角线上是否已经放置了皇后。
  原因：主对角线、副对角线各自平行（需要借助一定数学坐标公式，可推导其关系）

  
  2）、题解
  这里写法形式不固定，主要考验代码转化的能力。

class Solution {
    bool Col[10];// 用于检测某一竖列是否被放过皇后棋
    bool Dig1[20];// 用于检测主对角线
    bool Dig2[20];// 用于检测副对角线

    vector<vector<string>> ret;// 记录最终返回结果
    vector<string> path;// 记录单条路径（一种放置方案）
public:
    vector<vector<string>> solveNQueens(int n) {
        DFS(n, 0);
        return ret;
    }

    // 这里我们一行一行的递归放皇后棋
    void DFS(int n, int row)
    {
        if(row == n)
        {
            ret.push_back(path);
            return;
        }

        // 遍历当前行row，检测可以放在该行的哪一位置（哪一列）
        for(int i = 0; i < n; ++i)
        {
            // 当前位置处，列、两条斜线上均无皇后棋，表示可放置
            if(!Col[i] && !Dig1[row - i + n] && !Dig2[row + i])
            {
                // 放置一行的字符串
                Put(path, n, i);
                Col[i] = true;
                Dig1[row - i + n] = true;
                Dig2[row + i] = true;

                // 递归到下一行
                DFS(n, row + 1);

                // 递归回到当前层：回溯
                path.pop_back();
                Col[i] = false;
                Dig1[row - i + n] = false;
                Dig2[row + i]  = false;
            }
        }
    }

    void Put(vector<string>& path, int n, int pos)
    {
        string str;
        for(size_t i = 0; i < n; ++i)
        {
            if(i == pos)
                str += 'Q';
            else
                str += '.';
        }
        path.push_back(str);
    }
};

  另一种写法：也可以先将path棋盘初始化，那么深搜过程中，只需要考虑皇后棋Q如何放置即可。

class Solution {
    bool Col[10];// 用于检测某一竖列是否被放过皇后棋
    bool Dig1[20];// 用于检测主对角线
    bool Dig2[20];// 用于检测副对角线

    vector<vector<string>> ret;// 记录最终返回结果
    vector<string> path;// 记录单条路径（一种放置方案）
public:
    vector<vector<string>> solveNQueens(int n) {
        path.resize(n);// 直接开辟n个空间
        for(int i = 0; i < n; ++i)
        {
            path[i].append(n, '.');
        }
        DFS(n, 0);
        return ret;
    }

    // 这里我们一行一行的递归放皇后棋
    void DFS(int n, int row)
    {
        if(row == n)
        {
            ret.push_back(path);
            return;
        }

        // 遍历当前行row，检测可以放在该行的哪一位置（哪一列）
        for(int i = 0; i < n; ++i)
        {
            // 当前位置处，列、两条斜线上均无皇后棋，表示可放置
            if(!Col[i] && !Dig1[row - i + n] && !Dig2[row + i])
            {
                // 放置一行的字符串
                path[row][i] = 'Q';
                Col[i] = Dig1[row - i + n] = Dig2[row + i] = true;

                // 递归到下一行
                DFS(n, row + 1);

                // 递归回到当前层：回溯
                path[row][i] = '.';
                Col[i] = Dig1[row - i + n] = Dig2[row + i]  = false;
            }
        }
    }
};

  
  
  
  
  
  
  
  
  

14、有效的数独（medium）

  题源：链接。

  
  

14.1、题解

  1）、思路分析
  实则此题并非回溯类题型，放在这里主要是为了接下来的<解数独>做准备。

  我们只需要按照题目要求，从头遍历，在遇到元素是数字时，检验该元素出现的行、列、3×3小格内数值是否有效即可。 因此需要三个标记数组，用于标记行、列、3×3九宫格的情况：
  1、使用个二维数组来记录每个数字（共9个）在每行（共9行）中是否出现bool row[][]。同理，使用一个⼆维数组来记录每个数字在每列中是否出现bool col[][]。
  2、而对于3×3的九宫格，可以以行和列除以 3 得到的商作为九宫格的坐标，并使用一个三维数组来记录每个数字在每⼀个九宫格中是否出现 bool grid[3][3][]。

  
  
  2）、题解
  注意学习理解这里的标记数组使用。

class Solution {
    bool row[9][10];// 用于标记行，0~8这9行中，数字1~9是否存在。这里二维数组行表示数独中的行，列表示可在该行中填入的数字。
    bool col[9][10];// 用于标记0~8这9列中出现过的数字
    bool grid[3][3][10];// 3X3的小格，用于标记0~9这些数字在某一3X3小格中出现的情况
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i = 0; i < 9; ++i )
        {
            for(int j = 0; j < 9; ++j)
            {
                // 判断当前位置处是否填入数字
                if(isdigit(board[i][j]))
                {   //若当前位置为数字，判断其是否为有效的数独数
                    int num = board[i][j] - '0';//获取字符对应的数字。
                    int gridrow = i / 3;//获取当前(i,j)位于第几个3X3的小格中
                    int gridcol = j / 3;

                    // 判断当前这三处位置是否出现数字num
                    if(!row[i][num] && !col[j][num] && !grid[gridrow][gridcol][num])// 这里的if判断条件也可以反过来写
                    {
                        // 若均未出现，则标记，方便后续遍历时查找判断
                        row[i][num] = col[j][num] = grid[gridrow][gridcol][num] = true;
                    }
                    else
                        return false;// 若出现了，表示不满足有效数独，直接返回。

                }
            }
        }
        return true;
    }
};

  
  
  
  
  
  
  

15、解数独（hard）

  题源：链接。

  
  

15.1、题解

  1）、思路分析
  有了上题有效数独，可以为我们提供判断当前数独是否有效的思路，本题是在其基础上加上了决策操作。
  根据题目，数独部分空格内已填入了数字。因此，我们可以先遍历一遍矩阵board，将所有已经存放的数字在相应的行、列、九宫格标记数组中先做标记（表示该行/列/九宫格中，已经填过这个数）。然后从头遍历，对每个待填位置，穷举1~9填入，如此层层递归决策，判断是否合法。

  这里我们可以直接修改board[i][j]中的元素值，由于题目数据 保证输入数独仅有一个解，若遇到不合法的决策(无解)时，需要把board[i][j]的值复原。因此，递归遍历的DFS可以传递一个bool类型的返回值。
  
  
  2）、题解

class Solution {
    bool Col[9][10];// 用于确定列
    bool Row[9][10];// 用于确定行
    bool grid[3][3][10];// 3×3小格
    
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] != '.')
                {
                    int num = board[i][j] -'0';
                    Row[i][num] = Col[j][num] = grid[i/3][j/3][num] = true;
                }
            }
        }
        DFS(board);
    }

    bool DFS(vector<vector<char>>& board)
    {
        // 从头开始遍历找待填数位置
        for(int i = 0; i < 9; ++i)// row:第i行
        {
            for(int j = 0; j < 9; ++j)// col:第j列
            {
                if(board[i][j] == '.')
                {
                    //暴力穷举填数
                    for(int num = 1; num <=9; ++num)
                    {
                        if(!Row[i][num] &&  !Col[j][num] && !grid[i/3][j/3][num])
                        {
                            board[i][j] = num + '0';
                            Row[i][num] = Col[j][num] = grid[i/3][j/3][num] = true;
                            bool ret = DFS(board);//继续下一层递归
                            if(ret) return true;
                            else // 若下层递归返回false，说明此种写法的延续下得不到数独的解，换一个数尝试
                            {   //在进行下一次尝试之前，需要先把这里的标记恢复（恢复现场）
                                board[i][j] = '.';
                                Row[i][num] = Col[j][num] = grid[i/3][j/3][num] = false;
                            }
                        }
                    }
                    return false;// 来到此处，说明所有num值都试过，不满足要求，返回false
                }
            }
        }
        return true;
    }
};

  
  
  
  
  
  
  

16、单词搜索（medium）

  题源：链接。

  
  

16.1、题解

  1）、思路分析
  以board矩阵中每个位置的元素作为起始搜索的第一个字母，通过深度优先搜索的方式向相邻的四个方向进行递归，不断地枚举相邻元素作为下一个字母出现的可能，并在递归结束时回溯。当枚举完所有可能性，得到最终结果。（注意：向四周递归过程中，不能重复使用同⼀个位置的元素）

  
  2）、题解
  对于如何向四周递归，这里给出了两种写法： 其一为写四次if语句，依此递归判断上、下、左、右四个位置。其二为借助坐标向量间的关系。但无论哪一种，其总体宏观思路一致。
  
  写法一：

class Solution {
    bool visited[7][7];
    int m,n;
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(); // m行
        n = board[0].size();// n列
        for(int i = 0; i < m; ++i) 
        {
            for(int j = 0; j < n; ++j)
            {
                // 从头开始逐个遍历，找符合word首字母的元素，进行递归
                if(board[i][j] == word[0])
                {
                    visited[i][j] = true;
                    bool ret = DFS1(board, word, 1, i, j);
                    //bool ret = dfs(board, i, j, word, 1);
                    if(ret) return true;// 若某一位置找到满足条件的单词，直接返回
                    visited[i][j] = false;
                }
            }
        }
        return false;// 矩阵遍历完仍旧未找到符合word的字母。
    }

    // 当前回合递归，从(i,j)位置开始，横向纵向， 寻找字母word[pos]。
    bool DFS1(vector<vector<char>>& board, string& word, int pos, int i, int j)
    {
        // 递归结束条件
        if(pos >= word.size())
            return true;

        // 从board(i,j)位置，向四周扩散寻找符合要求的字符(注意边界检查)
        
        if(j-1 >= 0 && !visited[i][j-1] && board[i][j-1] == word[pos])
        {   // 找左：满足条件，则继续向下层递归
            visited[i][j-1] = true;
            int ret = DFS1(board, word, pos + 1, i, j -1);
            if(ret) return true;
            // 若下层递归不满足，回溯恢复现场，继续找其它位置
            visited[i][j-1] = false;
        }
        if(j+1 < board[0].size() && !visited[i][j+1] && board[i][j+1] == word[pos])
        {
            // 找右：
            visited[i][j+1] = true;
            int ret = DFS1(board, word, pos + 1, i, j + 1);
            if(ret) return true;
            visited[i][j+1] = false;
        }
        if(i-1 >= 0 && !visited[i-1][j] && board[i-1][j]== word[pos])
        {
            // 找上： 
            visited[i-1][j] = true;
            int ret = DFS1(board, word, pos + 1, i - 1, j);
            if(ret) return true;
            visited[i-1][j] = false;
        }
        if(i+1 < board.size() && !visited[i+1][j] && board[i+1][j]== word[pos])
        {
            // 找下：
            visited[i+1][j] = true;
            int ret = DFS1(board, word, pos + 1, i + 1, j);
            if(ret) return true;
            visited[i+1][j] = false;
        }

        // 如果(i,j)的上下左右位置均寻找后不满足条件，那么当前位置选择错误，返回false重新定位
        return false;
    }
};

  
  写法二：二维数组暴搜递归常常需要借助这种数组，建议学习其写法。

class Solution {
    bool visited[7][7];
    int m,n;
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(); // m行
        n = board[0].size();// n列
        for(int i = 0; i < m; ++i) 
        {
            for(int j = 0; j < n; ++j)
            {
                // 从头开始逐个遍历，找符合word首字母的元素，进行递归
                if(board[i][j] == word[0])
                {
                    visited[i][j] = true;
                    bool ret = DFS1(board, word, 1, i, j);
                    //bool ret = dfs(board, i, j, word, 1);
                    if(ret) return true;// 若某一位置找到满足条件的单词，直接返回
                    visited[i][j] = false;
                }
            }
        }
        return false;// 矩阵遍历完仍旧未找到符合word的字母。
    }

    // 用向量的⽅式，定义上下左右四个位置
    // 左(i,j-1)、右(i,j+1)、上(i-1,j)、下(i+1,j)
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};


    // 当前回合递归，从(i,j)位置开始，横向纵向， 寻找字母word[pos]。
    bool DFS(vector<vector<char>>& board, string& word, int pos, int i, int j)
    {
        // 递归结束条件
        if(pos >= word.size())
            return true;

        // 从board(i,j)位置，向四周扩散寻找符合要求的字符(注意边界检查)
        for(int k = 0; k < 4; ++k)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m &&  y >= 0 && y < n &&  !visited[x][y] && board[x][y] == word[pos])
            {   // 找左：满足条件，则继续向下层递归
                visited[x][y] = true;
                bool ret = DFS(board, word, pos + 1, x, y);
                if(ret) return true;
                // 若下层递归不满足，回溯恢复现场，继续找其它位置
                visited[x][y] = false;
            }
        }

        // 如果(i,j)的上下左右位置均寻找后不满足条件，那么当前位置选择错误，返回false重新定位
        return false;
    }
};

  
  
  
  
  
  

17、黄金矿工（medium）

  题源：链接。

  
  

17.1、题解

  1）、思路分析
  有了对单词搜索那题的理解，这里的解题思路类似，区别在于附加了递归过程中要做的事：统计路径中的元素和，找值最大的路径。
  
  
  2）、题解
  细节处理写法一：这里是借助了标记数组bool visited[][]，表示探索过的路。若觉此处浪费空间，实则也可以使用一个变量解决，写法见下。
  同理这里的int path单条路径值也可以不设置为类成员变量，而是作为递归的参数传入。总之细节形式多样。

class Solution {
    int ret;// 用于记录最终返回的最大值
    int path;// 用于记录单条路径寻找的值
    bool visited[16][16];// 用于标记走过的路
    int m,n;
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();// m行
        n = grid[0].size();// n列
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j])//当前位置有黄金，以当前位置作为起点，向四周开采
                {
                    visited[i][j] = true;
                    path += grid[i][j];
                    DFS(grid, i , j);
                    visited[i][j] = false;
                    path -= grid[i][j];
                }
            }
        }

        return ret;
    }

    // 使用向量表示(i,j)四周位置:
    // 上(i-1,j)，下(i+1,j)，左(i,j-1)，右(i,j+1)
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = { 0, 0, -1, 1};

    void DFS(vector<vector<int>>& grid, int i, int j)
    {
        // 向(i,j)四周坐标寻找黄金
        for(int k = 0; k < 4; ++k)
        {   
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && 
            grid[x][y] && !visited[x][y])
            {
                visited[x][y] = true;
                path += grid[x][y];
                DFS(grid, x, y);
                path -= grid[x][y];
                visited[x][y] = false;
            }
        }
        // 若四周寻遍无黄金，路径结束返回。
        if(path > ret) ret = path;
    }
};

  
  细节处理写法二：int tmp = grid[x][y];借助一个变量记录当前位置的矿数，向下递归时，先将当前位置矿石改为0，这样后续向四周寻找时，就不会走到元素为空的位置处。递归返回时需要将其恢复现场。

class Solution {
    int ret;// 用于记录最终返回的最大值
    int path;// 用于记录单条路径寻找的值
    int m,n;
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();// m行
        n = grid[0].size();// n列
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j])//当前位置有黄金，以当前位置作为起点，向四周开采
                {
                    int tmp = grid[i][j];
                    grid[i][j] = 0;
                    path += tmp;
                    DFS(grid, i , j);
                    path -= tmp;
                    grid[i][j] = tmp;
                }
            }
        }

        return ret;
    }

    // 使用向量表示(i,j)四周位置:
    // 上(i-1,j)，下(i+1,j)，左(i,j-1)，右(i,j+1)
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = { 0, 0, -1, 1};

    void DFS(vector<vector<int>>& grid, int i, int j)
    {
        // 向(i,j)四周坐标寻找黄金
        for(int k = 0; k < 4; ++k)
        {   
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && 
            grid[x][y])
            {
                int tmp = grid[x][y];
                grid[x][y] = 0;
                path += tmp;
                DFS(grid, x , y);
                path -= tmp;
                grid[x][y] = tmp;
            }
        }
        // 若四周寻遍无黄金，路径结束返回。
        if(path > ret) ret = path;
    }
};

  
  
  
  
  
  

18、不同路径 Ⅲ（hard）

  题源：链接。

  
  

18.1、题解

  1）、思路分析
  

  
  2）、题解

class Solution {
    int step = 2;// 用于统计从1到2走完所有0所需要的步数（默认算入1、2两步）
    int ret = 0;// 用于记录最终合法路径数目
    bool visited[21][21];// 用于标记走过的方格
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int x,y;
        // 统计从1到2走完所有0所需要的步数：所有的方格0 + 方格1 + 方格2
        for(int i = 0; i < grid.size(); ++i)
        {
            for(int j = 0; j < grid[0].size(); ++j)
            {
                if(grid[i][j] == 0)
                    ++step;
                else if(grid[i][j] == 1)
                {
                    x = i; y = j;
                }
            }
        }
        visited[x][y] = true;
        DFS(grid, x, y, 1);// 将(x,y)加入步数中
        return ret;
    }

    // 上(x - 1, y)  下(x + 1,y)  左(x, y -1)  右(x, y + 1)
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    // 从当前(x,y)位置开始，向四周寻找路径
    void DFS(vector<vector<int>>& grid, int x, int y, int count)
    {
        if(grid[x][y] == 2)
        {
            if(count == step) ++ret;
            return;
        }

        for(int k = 0; k < 4; ++k)
        {
            int next_x = x + dx[k];
            int next_y = y + dy[k];
            if(next_x >=0 && next_x < grid.size() &&
             next_y >= 0 && next_y < grid[0].size() &&
             grid[next_x][next_y] != -1 && !visited[next_x][next_y])
             {
                visited[next_x][next_y] = true;
                DFS(grid, next_x, next_y, count + 1);// 将当前(next_x, next_y)加入步数中
                visited[next_x][next_y] = false;
             }
        }
        return;
    }
};

  
  
  
  
  
  
  
  
  
  

Fin、共勉。