Leetcode刷题笔记--回溯(back_tracking)_回溯模板

---

前言

回溯是一种算法思想，它采用试错的方法来解决问题。在解决问题的过程中，如果发现当前的选择不正确或者无法达到目标，就会撤销上一步或者上几步的计算，并尝试其他可能的选择。这种方法也被称为探索与回溯法，是一种选优搜索法，通过递归的方式向前搜索，达到目标后再逐步回退，以找到问题的解。

之前在学习二叉树的章节中，就对于有些回溯的过程有些模糊，为了对之后的图论打下基础，回溯是必须要好好掌握的。本文就参考代码回想录的回溯章节，循序渐进地进行学习！

一、回溯的基本模板

回溯的本质是穷举，穷举所有可能，然后选出想要的答案。在我看来，回溯最关键的点在于回溯法解决的问题都可以抽象为树形结构！ 如果能明白这一点，列出相关问题的树状结构，便可以更加清晰的解决问题。

回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。 从大方向来讲是对每个子集合的横向遍历，而通过递归对每个子集和不断往深处探寻！递归要有终止条件，所以必然是一棵高度有限的树（N叉树）。正如下图所示：

这样的话，对于回溯问题就有了对应的步骤：
1.确定返回值和参数
2.确定终止条件
3.回溯横向遍历宽度。合的大小构成了树的宽度，递归的深度构成的树的深度。
4.进行剪枝处理。

对应的代码模板如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

接下来对不同类型的题目进行回溯分析。

二、组合问题

1.组合问题
本题要求返回范围 [1, n] 中所有可能的 k 个数的组合。题目中已经暗含了信息，我们不能重复取数。按照这个要求，可以先画出本题目的树状结构，n为树的宽度，k为树的深度，以n=4,k = 2为例：

画出回溯树状图，就可以套用上面的模板了。可以发现，对于不同情况，树的宽度是不同的，这也就是我们需要更改的地方:将起始位置作为参数传入回溯函数中即可。
回溯函数的参数为n,k和起始位置start，返回为空。
当回溯的深度为2的时候，便可以返回。
之后进行宽度的for循环处理，在每次执行回溯函数之后，需要撤销本次操作，回到之前的状态。
具体的代码如下：

vector<vector<int>> ans;
vector<int> path;

void backtracking(int n, int k, int start)
{
    if (path.size() == k)
    {
        ans.push_back(path);
        return;
    }

    // for (int i = start; i <= n; i++)
    // 剪枝优化
    for (int i = start; i <= n - (k - path.size()) + 1; i++)
    {
        path.push_back(i);
        backtracking(n, k, i + 1);
        path.pop_back();
    }
}

// 组合
vector<vector<int>> combine(int n, int k)
{

    backtracking(n, k, 1);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

之后要考虑回溯最重要也是比较难想的部分：剪枝优化！ 因为回溯本质上是暴力搜索，只有剪枝的方法可以减少一些运算量。
对于本题来讲，剪枝的关键在于结果集合的长度。结果集合的长度等于树的深度，也就是k。可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。这里的筛选依据就是：**如果当前要遍历的集合长度小于剩余的长度，那么就可以进行排除，因为他已经不足以让我们得出结果了。**具体的代码更改如下：

// for (int i = start; i <= n; i++)
// 剪枝优化
for (int i = start; i <= n - (k - path.size()) + 1; i++)
1
2
3

这里参考代码随想录的图片，更好地理解：

2.组合总和3

为什么先做3呢，因为3和第一题更为类似，有种循序渐进的过程。本道题目就是更改了条件：找出所有相加之和为 n 的 k 个数的组合。很好理解，深度仍然是k，宽度是1-9，由于不能取重复元素，所以还是要设置一个起始位置。
之后只需要更改终止条件即可，终止条件仍为当前路径长度为k 。不过路径之和为n的话，储存结果。

本题的剪枝操作也比较好理解，当前路径总和大于n的话，直接就可以跳出了，因为再加上其他数只会更大，不能满足等于n的要求。下面图片更好理解。

int sum = 0;

void backtracking01(int k, int n, int start)
{
    if (sum > n)
    { // 剪枝操作
        return;
    }
    if (sum == n && path.size() == k)
    {
        ans.push_back(path);
        return;
    }
    if (path.size() == k)
        return;

    for (int i = start; i <= 9; i++)
    {
        path.push_back(i);
        sum += i;
        backtracking01(k, n, i + 1);
        path.pop_back();
        sum -= i;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3.电话号码的字母总和
本题与之前问题的不同之处在于：for循环中，每个数字对应的是不同的字母组合。 这就需要一个哈希表进行映射解决问题。
首先，本题中输入数字的长度，也就为k，表示树的回溯深度。之后确定树的宽度，由于不同的数字对应的字母数量也未必相同，所以直接使用下面语句即可。

for (auto d : phoneMap[digits[start]])
1

每次遍历完一个数字的所以字母之后，就需要对下一个数字进行处理，这时候更改回溯过程的起点即可。当回溯的起点到达字符串长度时候，说明到达了终点。储存结果，返回即可。之后回溯的撤销操作与之前类似。

vector<string> ans;
string path;
unordered_map<char, string> phoneMap{
    {'2', "abc"},
    {'3', "def"},
    {'4', "ghi"},
    {'5', "jkl"},
    {'6', "mno"},
    {'7', "pqrs"},
    {'8', "tuv"},
    {'9', "wxyz"}};

void backtrcking(int index, string s)
{

    if (index= s.size())
    {
        ans.push_back(path);
        return;
    }
    for (auto p : phoneMap[s[index]])
    {
        path.push_back(p);

        backtracking(index+ 1, s);
        path.pop_back();
    }
}

vector<string> letterCombinations(string digits)
{
    if (digits.size() == 0)
        return ans;
    backtracking(0, digits);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

4.组合总和

本题与之前组合总和3很近似，差别在于本题中的同一个数字可以无限制重复被选取 。 有点像01背包和完全背包的区别。
之前不能重复的话，树的宽度是随着深度的增加而不断减少的，如果取重复，那么每个树的宽度一直不变。这看起来复杂度就要爆炸。。最后还是需要进行剪枝操作，才能完成目标。

这道题主要讨论一下，是否需要start作为回溯函数的参数！ start通常作为每一层宽度的遍历起始位置。组合和组合总和3是求同一个集合中的组合，但是在同一个集合中不能取同一个元素，所以每次start会随深度进行变化。具体实现的代码是这样的:

    for (int i = start; i <= n; i++)
    {
        path.push_back(i);
        backtracking(n, k, i + 1);
        path.pop_back();
    }
1
2
3
4
5
6

每一层的i从start开始遍历，在for循环中，将i+1赋给start,这样就可以无重复选取了。
但是想要重复选取，并不是直接令i = 0，去掉start参数的！ 本题就是一个例子，如果直接写成

    for (int i = 0; i < candidates.size(); i++)
    {
		...
        backtracking(candidates, target);
		...
    }
1
2
3
4
5
6

这样会导致重复取数！ 例如candidates = {2，3，6，7}，target = 7。最终的结果会存在{2，2，3}，{3，2，2}，{2，3，2}三个结果，但是根据题意，这三种情况算是一种情况。为了避免这种情况的发生，我们每次获取的元素刚好包含当前元素，而不包含之前元素，这样的话就取得我们想要的结果了。最后应该写为：

    for (int i = start; i < candidates.size(); i++)
    {
		...
        backtracking(candidates, target,i);
		...
    }
1
2
3
4
5
6

之后的代码就好写了，代码如下：

vector<vector<int>> ans;
vector<int> path;
int sum;
void backtracking(vector<int> &candidates, int target, int start)
{

    if (sum > target)
        return;

    if (sum == target)
    {
        ans.push_back(path);
        return;
    }
    for (int i = start; i < candidates.size(); i++)
    {
        path.push_back(candidates[i]);
        sum += candidates[i];
        backtracking(candidates, target,start);
        path.pop_back();
        sum -= candidates[i];
    }
}

vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
    backtracking(candidates, target,0);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

本题的剪枝操作是判断sum>target，其实可以把这个判断提前，直接在for循环上剪枝，这样的话就不会多出这个判断的步骤。如果最开始对数组进行排序后，便可以直接在for循环中判断：

// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)
1
2

5.组合总和2
这道题目之所以作为组合问题的最后一个，说明这道题目是最难最麻烦的！！其实第一次写到这一题的时候我已经晕了，和上面的题目有些混淆。
这道题目与上面的组合总和不同之处在于：

1.本题candidates 中的每个数字在每个组合中只能使用一次。
2.本题数组candidates的元素是有重复的，而组合总和 (opens new window)是无重复元素的数组candidates。

总结来讲：数组中可以有重复的元素，但是不能有重复的组合！ 举个简单的例子，便于理解。

candidates = {1，3，1，2}，target = 4
1

这个时候，第一个1和第二个1都可以跟3进行组合，得到目标值。但是结果中我们只需允许出现一个{1,3}，这表明需要进行去重处理。但是数组中有重复的数组，所以{1，1，2}这个组合是合理的。
之后的工作，就是搞明白到底什么时候进行去重操作！代码随想录这个地方讲的很清晰。由于数组中可以有重复的元素，所以树枝不用去重，由于不能有重复的组合，所以树层需要进行去重！
关于树层去重，我的理解是这样的。假设事先对数组进行排序。

candidates = {1，1，2，3}，target = 4
1

那么遍历第一个1之后的数字中，肯定包含了从第二个1开始遍历的情况。也就是说，我们对第一个1节点进行深度搜索时候，已经搜索出了{1，3}这种情况，当对第二个1节点搜索时，也会搜出{1，3}这种情况！这就是重复的来源，我们需要进行处理：
当前元素与上一个元素相同时，就不搜索了，直接下一个！本题的关键去重代码是：

if (i > start && candidates[i] == candidates[i - 1])  continue;
1

这个代码后半部分很容易理解，是对树层进行处理。但是如果只有后半部分，那么结果也不允许树枝中有重复的元素，因此需要添加 i>start 这个限制条件。因为在树枝中进行搜索时候，如果出现相同的元素，i是等于start的(已经进行排序处理)。

/// @brief 组合总和2
vector<vector<int>> ans;
vector<int> path;
int sum2 = 0;
void backtracking04(vector<int> &candidates, int target,int start){

    if (sum2 > target)
        return;
    if (sum2 == target)
    {

        ans.push_back(path);
        return;
    }

    for (int i = start; i < candidates.size(); i++)
    {
        if (i > start && candidates[i] == candidates[i - 1])
        {
            continue;
        }
        path.push_back(candidates[i]);
        sum2 += candidates[i];
        backtracking04(candidates, target, i + 1);
        sum2 -= candidates[i];
        path.pop_back();
    }
    
}


    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
    ans.clear();
    path.clear();
    sort(candidates.begin(), candidates.end());
    backtracking04(candidates, target, 0);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

三、分割与子集问题

1.分割回文串

这是第一道分割问题，他同时与回文串结合，稍微增加了难度，不过通过按部就班的分析，还是能写出来的。我们先根据题意，列出树状结构。

在组合问题中，对于aab，如果第一个取a,那么之后可以从第二个a开始选取，可以选a或者ab。
对于本题分割问题，如果切割了第一个a，此时字符串变为a|ab，之后就可以从第二个a切割，可以选择继续切割或者不切割。结果为 a|ab,a|b|b。
可以发现，其实这两个问题本质是一样的，都是选取了当前的字符后，从下一个字符选取。然后我们再加上判断回文串。为了 满足所有子串都是回文串，那么如果当前串不论在哪一层，只要当前分割的串不是回文串，那就可以跳出了。

本题关键要记录当前分割出来的子串，然后进行判断：

string c = s.substr(start, i - start+ 1);
1

整体代码如下：

vector<vector<string>> res;
vector<string> pth;

bool is_Palindrome(string s)
{
    int n = s.size();
    if (n == 1)
        return true;
    int l = 0, r = n - 1;
    while (l < r)
    {
        if (s[l] == s[r])
        {
            l++;
            r--;
        }
        else
            return false;
    }
    return true;
}

void backtracking10(string s, int start)
{

    if (start== s.size())
    {
        res.push_back(pth);
        return;
    }

    for (int i = start; i < s.size(); i++)
    {
        string c = s.substr(start, i - start+ 1);
        if (is_Palindrome(c))
        {
            pth.push_back(c);
            backtracking10(s, i + 1);
            pth.pop_back();
        }
        else
            continue;
    }
}

vector<vector<string>> partition(string s)
{
    backtracking10(s, 0);
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

2.复原IP地址

这道问题有些复杂了，但还是上一题的变种。我们的目的是要把地址分割为4段，并且每段都是合法的。首先需要思考，分割为四段的判断条件是什么。这需要记录一下点的数量。当num_comma==4的时候，表明已经分割为四段，这时候进行一些合法的判断，看是否储存结果。本题的start是必须的，此外，为了进行终止条件的判断，我还加上了sub_size参数，表示子串的长度。回溯函数参数已经确定了：

void backtracking(string s, int start, int sub_size, int num_comma)
1

再看回溯函数的for循环，我首先记录当前子串，然后对他进行判断，如果不满足地址的要求，那么直接break.

if (stoi(cur) > 255 || (cur.size() > 1 && cur[0] == '0'))  break;
1

这里我使用的是break,有时候会使用continue。这是一个细节。关键在于当前子串不满足题意之后，是继续下一个循环过程，还是把以当前子串为起始位置的情况全部去除。
举个简单的例子：
当前子串大于255的话，那他接下来的2556，25567肯定已经大于255了。如果当前子串为01，那么接下来的011，0111也都不满足题意了。所以本体采用的是break。
接下来就是回溯过程了，这里的回溯过程显得有些许复杂，因为不止回溯了当前路径，还回溯了点的数量以及当前路径中的点：

road.append(cur);
road.append(".");
num_comma++;
backtracking11(s, i + 1, cur.size(), num_comma);
num_comma--;
road.pop_back();
road.erase(road.size() - cur.size());
1
2
3
4
5
6
7

最后再讲终止条件。关键在于排除一些情况。首先获取最后一个子串，不仅要判断是否是否小于255和不能以0开头，同时要保证最后一个字串是整个地址的最后。例如：
地址为：2552551101
那么我们肯定不能出现这种情况：
255.255.1.10
所以应该充分考虑所有情况，再把当前路径加入到结果：

    if (num_comma == 4)
    {
        string cur = road.substr(road.size() - 1 - sub_size, sub_size);
        if (stoi(cur) > 255 || (cur.size() > 1 && cur[0] == '0') || (road.size() - 4 < s.size()))
            return;
        else
        {
            string r = road;
            r.pop_back();
            result.push_back(r);
            return;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

至此，回溯函数已经完成了，整体的代码如下：

vector<string> result;
string road;

void backtracking(string s, int start, int sub_size, int num_comma)
{

    if (num_comma == 4)
    {
        string cur = road.substr(road.size() - 1 - sub_size, sub_size);
        if (stoi(cur) > 255 || (cur.size() > 1 && cur[0] == '0') || (road.size() - 4 < s.size()))
            return;
        else
        {
            string r = road;
            r.pop_back();
            result.push_back(r);
            return;
        }
    }

    for (int i = start; i < s.size(); i++)
    {
        string cur = s.substr(start, i - start + 1);
        if (stoi(cur) > 255 || (cur.size() > 1 && cur[0] == '0'))
            break;

        road.append(cur);
        road.append(".");
        num_comma++;
        backtracking11(s, i + 1, cur.size(), num_comma);
        num_comma--;
        road.pop_back();
        road.erase(road.size() - cur.size());
    }
}

/// @brief 复原IP地址
/// @param s
/// @return
vector<string> restoreIpAddresses(string s)
{

    backtracking(s, 0, 0, 0);
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

3.子集
之前的题目是在某个特定的情况下才将子集加入到结果，本题就更简单了，把所有子集都加入到结果中。主要关注的终止条件的变化。属于一道简单的模板题目。

vector<vector<int>> ans;
vector<int> path;

void backtracking(vector<int> &nums, int start)
{

    ans.push_back(path);

    for (int i = start; i < nums.size(); i++)
    {

        path.push_back(nums[i]);
        backtracking(nums, i + 1);
        path.pop_back();
    }
}

vector<vector<int>> subsets(vector<int> &nums)
{

    backtracking(nums, 0);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4.子集2

本题似乎与组合总和2有些异曲同工之妙。解答这个题的关键还是：树枝不用去重，树层需要去重！ 之前的题目理解了，这道题就会了，只需加上一句话：

 if (i != start && nums[i] == nums[i - 1]) continue;
1

需要注意的是，原数组需要排序，这样才能使相同的元素是相邻的。

vector<vector<int>> ans;
vector<int> path;

void backtracking(vector<int> &nums, int start)
{

    ans.push_back(path);

    for (int i = start; i < nums.size(); i++)
    {
        if (i != start && nums[i] == nums[i - 1])
            continue;
        path.push_back(nums[i]);
        backtracking(nums, i + 1);
        path.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int> &nums)
{
    sort(nums.begin(), nums.end());
    backtracking(nums, 0);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四、排序问题

1.全排列
我们可以发现，排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合。可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。先画出树状结构：

很容易想到，需要设置一个used数组，记录哪个数已经被使用了，因为在一个排列中，不能出现相同的数字。used设置为和nums大小相同的布尔型数组，如果当前元素使用过了，那就continue，继续判断其他数字，如果当前元素没有被使用，那就使用它，并且置1.记得回溯过程中把当前重新置零即可。代码上也很容易实现：

vector<vector<int>> ans;
vector<int> path;

void backtracking11(vector<int> &nums, vector<bool> used)
{
    if (path.size() == nums.size())
    {
        ans.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++)
    {

        if (used[i] == 1)
            continue;
        else
            used[i] = 1;
        path.push_back(nums[i]);
        backtracking11(nums, used);
        used[i] = 0;
        path11.pop_back();
    }
}

vector<vector<int>> permute(vector<int> &nums)
{
    vector<bool> used(nums.size(), 0);
    backtracking11(nums, used);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.全排列2

这只需要修改一下used数组就可以啦，之前数组中元素不同，只有可能为0,1。而现在数组中有相同的元素了，要判断当前元素是否到达所有使用次数，才能不使用这个元素。这时候使用哈希表是很合适的选择，太妙了！

vector<vector<int>> ans;
vector<int> path;

void backtracking(vector<int> &nums, unordered_map<int, int> &used)
{
    if (path.size() == nums.size())
    {
        ans.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++)
    {
        if (i > 0 && nums[i] == nums[i - 1])
        {
            continue;
        }

        if (used[nums[i]] <= 0)
            continue;

        else
            used[nums[i]]--;

        path.push_back(nums[i]);
        backtracking11(nums, used);
        used[nums[i]]++;
        path.pop_back();
    }
}

vector<vector<int>> permuteUnique(vector<int> &nums)
{
    unordered_map<int, int> used;
    for (auto c : nums)
        used[c]++;
    sort(nums.begin(),nums.end());
    backtracking11(nums, used);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

四、棋盘问题

1.N皇后
做了之前回溯相关的题目，感觉N皇后也没有那么复杂了。本题当然可以抽象为一个树状结构。NN的棋盘赋予了本题一些特殊的属性。
1.首先，要想把N个皇后放到NN的棋盘中，这就需要满足每一行放置一个N皇后 ，因为不可能有一行放置两个皇后的情况出现。类似的，对于列也是一样的。
2.每一行的N种放置情况可以作为回溯函数中的循环，而回溯的深度就等于总共有多少行。
3.之前行数中放置的皇后位置会影响当前行放置皇后的位置，这需要我们记录之前行皇后的位置。由于皇后的对角线属性，我们需要记录两个关键参数，皇后所在的的行数和列数。

经过上述分析，接下来代码的思路就很清晰了。我个人觉得难点在于如何记录之前皇后的位置，从而判断当前行的哪个位置可以放置皇后。

1.首先当前行的列数不能与之前所有皇后的列数一样。这是一个判断条件。
之前所有皇后两侧对角线延伸到本行的位置不能放置皇后。

如果每次记录当前行哪个位置不能放置皇后，那么需要对这个记录同样进行回溯操作，但是当前行并不只受到有上一行的影响，同时受到之前所有行的影响，这样的话回溯的操作将会异常复杂。其实我们可以记录一下当前棋盘的状态，然后判断当前的行和列确定的点能否放置皇后即可，这里只需要一个判断函数，从而避免了将这个判断加入到回溯的过程中。

bool isValid(int row, int col, vector<string> &chessboard, int n)
{
    // 检查列
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

之后的回溯代码如下，回溯函数的参数需要包含当前的行，而我们的列通过回溯中的循环改变。这样就确定了当前点的行和列，即可进行是否合法的判断。

vector<vector<string>> ways;
bool isValid(int row, int col, vector<string> &chessboard, int n);
void queentracking(int n, int row, vector<string> chess)
{

    if (row == n)
    {
        ways.push_back(chess);
        return;
    }

    for (int col = 0; col < n; col++)
    {
        if (isValid(row, col, chess, n))
        {                          // 验证合法就可以放
            chess[row][col] = 'Q'; // 放置皇后
            queentracking(n, row + 1, chess);
            chess[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}


vector<vector<string>> solveNQueens(int n)
{
    std::vector<std::string> chess(n, std::string(n, '.'));
    queentracking(n, 0, chess);
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2.解数独
对于数独，我记得有一个通用的做法。对于每个空应该填写什么数字，有一个规则限制：

1.同一行不能出现相同的数
2.同一列不能出现相同的数
3.同一个小九宫格不能出现相同的数
4.要填写的数必须是1-9.

我们可以通过上面的规则，将当前的空格的数字筛选为更少的预选项。当我们把所有的空预选的数字都得出来时候，必定有一个空只有一个预选数字，那么他就应该填写为当前数字。之后的连锁反应可以减少其他空格的预选项，直到另一个空中只剩下一个预选数字，以此类推。

现在回想起来，这就是一个穷举的过程，但如果将他转化为回溯的思路的话，那就是将第一个空的每个预选数字进行模拟，看是否满足结果，不满足的话就退回，满足的话就继续遍历其他的空，从而实现整个回溯过程。

可问题在于，我们要填满整个9*9的空才算完成了一次回溯过程。这与上一题有些不同，上一题一行只能放置一个皇后，所以回溯的for循环中只需要遍历列即可。而本题很明显需要两个for循环，不仅要遍历每行，也要遍历每列。只要能想到这一点，其余的做法基本和N皇后相同了。
先写出回溯函数的流程，这还挺好实现的：

bool sudotracking(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 = '0'; k < '9'; k++)
            {
                if (isValid(i, j, k, board))
                {
                    board[i][j] = k;
                    if (sudotracking(board))
                        return true;
                    board[i][j] = '.';
                }
            }
        }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

之后编写判断是否合法的函数，这个函数的规则就参考开头说的那几条：

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这样就完成了代码的编写！看来这吓人的解数独也没这么难。

总结

写到这里，已经感觉回溯算法并不算很难，因为他有一个固定的模板和套路，关键的思想就是把问题抽象为树，然后分析思考，编写回溯函数。

在学习回溯章节时候，我觉得回溯的剪枝过程是很有趣的 ，具体在哪个位置剪枝，如何剪枝，树枝剪枝和树层剪枝。。这些都值得思考和慢慢品味。同时，还有能否取重复元素，重复元素的不同组合，start参数的如何选择，这也是很关键的。最好是在编写代码中不断调试，观察回溯函数的变化，因为他是很抽象的，调试可以发现大部分问题并且改正。

对于上述的相关题型，组合，分割，子集，排序，棋盘，这每一类问题都有不同的特性，但在大部分层面又有相似之处，具体的分析就在上面博客之中，希望之后可以慢慢品味！