跳转至

回溯基础练习

约 6781 个字 1070 行代码 11 张图片 预计阅读时间 36 分钟

本篇介绍

在前面回溯理论基础部分已经了解到回溯代码的基本结构以及其可以解决的一些问题，接下来就是将回溯算法的思路和框架代入到具体的题目，对于不同的题目代码的框架可能会有所改变，但是整体的结构不会有很大的改变。同样，为了更容易理解，本篇将按照回溯理论基础部分的分类对题目进行区分

组合问题

所谓组合问题，就是根据题目给定的范围以及每个组合的个数，求出有多少种满足条件的情况，例如假定有闭区间[1,4]，求出这4个数字每两个进行组合的所有情况

根据决策树可以画出所有的情况如下：

需要注意的是，因为求的是组合，所以不用在乎每一个组合中两个元素的顺序，例如[1,2]和[2,1]属于同一个组合，根据这个特点，因为开始时是从1开始枚举，所以一定是先出现[1,2]，再出现[2,1]，所以为了避免重复，在枚举2时就不可以再包括1，而是枚举2之后的数值，在代码逻辑中体现的就是下标向后移动

根据上面的描述，考虑组合问题用代码解决的思路，因为对于每一个数都是枚举，同样的逻辑就可以考虑循环或者递归进行解决，但是此处使用递归而不是循环，本质原因就是无法确定循环的嵌套层数

如果是上面例子中的4个数字，那么就需要至少4层循环，如果5个数字乃至n个数字，循环的层数就会变多，并且也会因为无法通过变量控制循环的层数导致无法直接使用循环解决。而递归之所以可以解决，本质就是利用了递归是新的执行逻辑，如果当前函数有一层循环，在该层循环中使用递归就相当于在该层循环中再嵌套一层循环，此时只需要确保结束条件正确就可以保证嵌套的循环的层数，这个思路在接下来的题目中也会有所体现

力扣77.组合

力扣77.组合

问题描述：

Quote

给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
输入：n = 4, k = 2
输出：
[
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
]

示例 2：

C++
1
2
输入：n = 1, k = 1
输出：[[1]]

思路分析：

本题就是典型的组合问题，思路在前面对组合问题的介绍已经提到过，接下来就是具体确定函数如何编写。因为任何递归都是都终止条件的，所以通过样例可以发现本题的终止条件就是层数，在前面的例子中一组数的个数只需要两个，所以只需要每一组执行一次函数递归一次即可。但是循环的起始位置必须是可变的，因为要根据调用者的下标取出其后面的数值，所以可以使用一个参数传递给递归函数，即为start。当递归要返回时，说明此时已经有了一个组合，将该结果插入到结果集再返回即可，返回到主调函数一定要删除上一个组合的最后一个数据，因为循环还要继续执行，继续向后插入数据，如果不删除上一次的最后一个数字，就会出现一直向后插入的现象

思路优化：剪枝

所谓剪枝，就是去掉一些多余的遍历过程，因为这些过程一定没有正确答案，例如前面例子中的最后一个数字4，无法构成组合，所以这种情况就可以去掉，这个动作就是剪枝。在求取组合的过程中可以发现，如果剩余的元素个数加上当前的元素不足以满足一个组合需要的元素个数，此时就一定不会存在结果，根据这个特点也就可以进行剪枝，所谓的「如果剩余的元素个数加上当前的元素不足以满足一个组合需要的元素个数」，也就是说元素总个数-（一个组合需要的元素个数-已经拿到的元素个数）+1如果小于当前下标就一定不存在结果

其中上面的表达式的意思就是：「一个组合需要的元素个数-已经拿到的元素个数」表示构成一个组合还需要多少元素，总数减去需要的元素个数+1就是算出最多能取到的元素的位置，即假设path为一个组合的集合，有n-(k-path.size())+1，注意因为左闭右闭，所以需要加1

在回溯问题中，因为其本身也是暴力算法，既然选择使用回溯，就说明没有其他的更优解，此时剪枝就是在枚举所有情况时的唯一一个优化方案

参考代码：

C++
 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
class Solution77_1
{
public:
    vector<vector<int>> ret;
    vector<int> path;

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

        for (int i = start; i <= n; i++)
        {
            path.push_back(i);
            // 函数递归回到此处，path中依旧存在着两个元素，因为进入前的现场就是两个元素
            backtracking(n, k, i + 1);
            // 恢复现场——path只有一个元素时，进入下一次循环
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k)
    {
        backtracking(n, k, 1);
        return ret;
    }
};
C++
 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
class Solution77_2
{
public:
    vector<vector<int>> ret;
    vector<int> path;

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

        // 缩小i的循环范围
        for (int i = start; i <= (n - (k - path.size()) + 1); i++)
        {
            path.push_back(i);
            // 函数递归回到此处，path中依旧存在着两个元素，因为进入前的现场就是两个元素
            backtracking(n, k, i + 1);
            // 恢复现场——path只有一个元素时，进入下一次循环
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k)
    {
        backtracking(n, k, 1);
        return ret;
    }
};

力扣216.组合总和Ⅲ

力扣216.组合总和Ⅲ

问题描述：

Quote

找出所有相加之和为n的k个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字最多使用一次 返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

C++
1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

C++
1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

C++
1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

思路分析：

本题基本思路和上一题一致，唯一不同的是递归结束条件，假设path为每一个组合结果集，sum表示当前path中所有元素的和，所以包括path长度和sum都满足要求，另外在枚举每一种情况时需要更新path和sum，递归结束后需要恢复path和sum，直到找到满足的情况才将path插入到结果集中

思路优化：剪枝

本题的剪枝很明显，如果sum已经大于目标值n时就不需要再向后递归了，除了上面的剪枝外，与上一题一样也有对循环的次数进行剪枝

参考代码：

C++
 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
class Solution216_1
{
public:
    vector<vector<int>> ret;
    vector<int> path;

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

        for (int i = start; i <= 9; i++)
        {
            path.push_back(i);
            sum += i;
            backtracking(k, n, sum, i + 1);
            path.pop_back();
            sum -= i;
        }
    }

    vector<vector<int>> combinationSum3(int k, int n)
    {
        backtracking(k, n, 0, 1);
        return ret;
    }
};
C++
 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
class Solution216_2
{
public:
    vector<vector<int>> ret;
    vector<int> path;

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

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

    vector<vector<int>> combinationSum3(int k, int n)
    {
        backtracking(k, n, 0, 1);
        return ret;
    }
};

力扣17.电话号码的字母组合

力扣17.电话号码的字母组合

问题描述：

Quote

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。

示例 1：

C++
1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

C++
1
2
输入：digits = ""
输出：[]

示例 3：

C++
1
2
输入：digits = "2"
输出：["a","b","c"]

思路分析：

本题的基本思路是建立数字和字符串映射，第一层循环枚举最开始的数字数组，第二层循环枚举其中的字符。因为一个组合中的每个字符来自不同的按键，所以递归时需要更改数字数组，但是对于映射的字符数组来说，每一次更新i，其都是从0下标开始向后枚举，所以此处是固定的操作

写法优化：

基本思路还是与上面的解法一致，但是对于写法可以进行简化。首先是映射，使用数组代替原来的哈希表，影响不大。在第一种写法中，函数通过循环和变量startOfDigits判断当前在digits数组的哪一个位置，但是实际上这一步可以交给递归来做，即每一次递归时通过更新下标，即可获取到新的数字对应的字符串数组，从而可以少写一个循环并且少用一个变量；接着是循环中的优化：因为递归前需要更新每一个组合path，可以考虑不改变当前的path，而是将path+新的字符构成一个新的临时对象传递给参数，此时就可以做到自动回溯而不是手动回溯

参考代码：

C++
 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
class Solution17_1
{
public:
    vector<string> ret;
    string path;

    void backtracking(string &digits, int startOfDigits, unordered_map<char, string> &dc)
    {
        if (path.size() == digits.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = startOfDigits; i < digits.size(); i++)
        {
            for (int j = 0; j < dc[digits[i]].size(); j++)
            {
                path += dc[digits[i]][j];
                backtracking(digits, i + 1, dc);
                path.pop_back();
            }
        }
    }

    vector<string> letterCombinations(string digits)
    {
        if (!digits.size())
            return ret;
        // 建立数字和字母映射
        unordered_map<char, string> dc;
        dc.insert({'2', "abc"});
        dc.insert({'3', "def"});
        dc.insert({'4', "ghi"});
        dc.insert({'5', "jkl"});
        dc.insert({'6', "mno"});
        dc.insert({'7', "pqrs"});
        dc.insert({'8', "tuv"});
        dc.insert({'9', "wxyz"});

        backtracking(digits, 0, dc);

        return ret;
    }
};
C++
 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
class Solution17_2
{
public:
    vector<string> ret;
    // 数组映射
    const string dc[10] = {
                "", // 0
                "", // 1
                "abc", // 2
                "def", // 3
                "ghi", // 4
                "jkl", // 5
                "mno", // 6
                "pqrs", // 7
                "tuv", // 8
                "wxyz", // 9
            };

    void backtracking(const string &digits, int index, string path)
    {
        if (index == digits.size())
        {
            ret.push_back(path);
            return;
        }

        // 获取对应的字符串
        int digit = digits[index] - '0';
        string letter = dc[digit];

        for (int i = 0; i < letter.size(); i++)
            backtracking(digits, index + 1, path + letter[i]);
    }

    vector<string> letterCombinations(string digits)
    {
        if (!digits.size())
            return ret;

        string path;
        backtracking(digits, 0, path);

        return ret;
    }
};

力扣39.组合总和

力扣39.组合总和

问题描述：

Quote

给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为target的不同组合数少于150个。

示例 1：

C++
1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

C++
1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

C++
1
2
输入: candidates = [2], target = 1
输出: []

思路分析：

本题与前面的组合问题最大的不同点就是每个元素可以被多次使用，即一个组合结果集中，同一个数字可以被重复使用多次，但是其本质还是一个组合，只是因为多了「可以重复使用元素」的条件，使得每一次搜索应该从上一次搜索的位置继续向后，而不是全部从头开始，更不是像之前的直接从后一个元素进行搜索

思路优化：剪枝

排序后可以使得原数组的元素单调递增，如果当前元素加上当前和sum已经大于target，那么后面的元素也就不需要再遍历了。注意此处的排序不可以省略，因为如果只是判断sum + 当前元素大于target就不再向后遍历时，就可能会出现后面存在小的元素可以确保sum + 小的元素等于target

参考代码：

C++
 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
class Solution39_1
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    void backtracking(vector<int> &candidates, int target, int sum, int index)
    {
        // 防止栈溢出
        if (sum > target)
            return;
        // 更新结果
        if (sum == target)
        {
            ret.push_back(path);
            return;
        }

        for (int i = index; i < candidates.size(); i++)
        {
            path.push_back(candidates[i]);
            sum += candidates[i];

            backtracking(candidates, target, sum, i);
            path.pop_back();
            sum -= candidates[i];
        }
    }

    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        backtracking(candidates, target, 0, 0);

        return ret;
    }
};
C++
 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
class Solution39_2
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    void backtracking(vector<int> &candidates, int target, int sum, int index)
    {
        // 防止栈溢出
        if (sum > target)
            return;
        // 更新结果
        if (sum == target)
        {
            ret.push_back(path);
            return;
        }

        for (int i = index; i < candidates.size() && sum + candidates[i] <= target; i++)
        {
            path.push_back(candidates[i]);
            sum += candidates[i];

            backtracking(candidates, target, sum, i);
            path.pop_back();
            sum -= candidates[i];
        }
    }

    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);

        return ret;
    }
};

力扣40.组合总和Ⅱ

力扣40.组合总和Ⅱ

问题描述：

Quote

给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。

candidates中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

C++
1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
]

示例 2:

C++
1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
    [1,2,2],
    [5]
]

思路分析：

本题的基本思路还是计算总和sum等于target的组合，但是因为本题给定的数组存在重复的元素，所以不但需要注意每一个组合在不考虑元素顺序的情况下不重复以外，还要考虑在获取到不同位置的元素但是元素值前面已经出现过时再次选取导致的组合重复，所以本题最大的难点就在于如何进行去重

本题的去重方式可以从两个方面考虑： 1. 树层去重：针对同一层的元素进行去重 2. 树枝去重：针对同一条路径的元素进行去重

以[10,1,2,7,6,1,5]，target为8为例：

为了实现上面的去重逻辑，需要一个数组used，表示每一个元素是否被使用，值只有true或者false，并且需要对给定集合进行排序，之所以需要使用到排序，就是为了确保相同的元素可以出现在一起，即[1,1,2,5,6,7,10]，used=[false,false,false,false,false,false,false]。因为本题可以做到不同位置但是值相同的元素出现在同一个组合中，此时例如[1,1,6]在used数组中就会表现为[true, true, true]，而对于这种情况来说，不需要也不可以进行去重，一旦去重就会忽略后面的6导致缺少一个组合结果，所以可以不需要考虑进行树枝去重

但是需要考虑树层去重，因为存在两个1，如果使用第一个1，此时在同一层下，第二个1就是未使用状态，此时used就是[true,false...]，对于这种情况，第一次搜索1，一定会搜索到[1,7]，但是因为7也存在与第二个1的后面，所以第二个1遍历也会搜索到[1,7]，虽然使用的是不同位置的1，但是最后的组合结果是一样的，所以此时就需要去重，但是最后的组合结果是一样的，所以此时就需要去重

参考代码：

C++
 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
class Solution40
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    void backtracking(vector<int> &candidates, int target, int sum, int start, vector<bool> &used)
    {
        if (sum > target)
            return;
        if (sum == target)
        {
            ret.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size(); i++)
        {
            // 去重逻辑-树层去重但不进行树枝去重，判断used[i - 1] == false就是为了防止对树枝也进行了去重
            if (i - 1 >= 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
                continue;

            path.push_back(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used);
            path.pop_back();
            sum -= candidates[i];
            used[i] = false;
        }
    }

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<bool> used(candidates.size(), 0);
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);

        return ret;
    }
};

力扣332.重新安排行程

力扣332.重新安排行程

问题描述：

Quote

给你一份航线列表tickets，其中tickets[i] = [fromi, toi]表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从JFK开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程["JFK", "LGA"]与["JFK", "LGB"]相比就更小，排序更靠前。 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

C++
1
2
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

C++
1
2
3
输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

思路分析：

本题是典型的欧拉回路问题，但是本题也可以用回溯解决

  1. 解法1：回溯 本题的思路就是通过出发地找出合适的目的地，因为需要遍历到所有情况，所以可以利用回溯来解决。因为题目中提到，如果存在多种路径，那么就按照字典序排序，所以可以考虑将目的地放入map中。本题因为给定了出发地为JFK，所以从该出发地一定可以找到对应的目的地，再将下一次的目的地作为出发地一直向下寻找，直到找到一条合适的路径直接向上返回即可

    本题可能出现两种情况：

    1. 一条路走到黑
    2. 有循环航班

    以下面三个例子为例：

    1. [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]（一条路走到黑）
    2. [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]（简单的循环航班）
    3. [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]（复杂的循环航班）

    首先对于第一种情况来说，如下图所示：

    对于第二种情况来说，如下图所示：

    以同样的方式也可以得出第三种情况的答案

  2. 解法2：欧拉回路问题

    见算法：图论

参考代码：

C++
 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution332
{
public:
    // 处理目的地出现次数、目的地映射
    // map<string, int> 目的地与出现次数映射，防止过量使用同一个目的地，并且使用map默认会进行升序排序
    // 将出发地与目的地进行映射
    // unordered_map<string, string> 出发地与目的地映射
    // 将上面两种映射结合，做到通过出发地在map中获取到目的地，获取到目的地后通过map映射获取到票数
    unordered_map<string, map<string, int>> dest;
    // 结果集
    vector<string> ret;

    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        // 建立映射并更新票数
        for (auto &path: tickets)
        {
            // dest[path[0]]表示出发地和目的地进行映射，当前目的地为空
            // dest[path[0]][path[1]]通过出发地获取到目的地，再通过目的地更新票数计数
            dest[path[0]][path[1]]++;
        }

        // 参数为当前使用的票数
        // 因为只需要找到任意一条符合条件的路径就可以直接返回，所以当找到时一直向上层返回true即可
        function<bool(int)> backtracking = [&](int ticketNum)
        {
            // 经过地个数=票数+1
            // 找到一条符合的路径直接返回，不需要再继续向下找
            if (ret.size() == ticketNum + 1)
                return true;

            // 根据出发地获取到目的地，如果目的地的票数仍然大于0，说明还可以走
            // 每一次循环时，出发地就是结果集中最后一个元素
            // 因为map中已经排序，所以获取时也是按照字典序获取
            // 注意string要加const，否则编译报错
            for (pair<const string, int> &p: dest[ret[ret.size() - 1]]) // map<string, int>
            {
                // 票数大于0
                if (p.second > 0)
                {
                    // 走到目的地
                    ret.emplace_back(p.first);
                    // 减少票数
                    p.second--;
                    // 如果找到一条路径，就一直向上返回
                    if (backtracking(ticketNum))
                        return true;

                    // 回溯
                    ret.pop_back();
                    p.second++;
                }
            }

            return false;
        };

        // 开始时一定从JFK机场出发
        ret.emplace_back("JFK");

        backtracking(tickets.size());

        return ret;
    }
};

切割问题

切割问题本质也算是组合问题，但是其不仅仅涉及到了组合，还涉及到如何进行切割，例如切割一个字符串使其可以满足某一种条件，在下面的题目中会揭晓对应的切割思路。同样，对于分割问题，首先还是要思考为什么不可以直接用迭代法解决，因为分割的本质实际上就是确定一个范围，取出该范围内的结果进行判断，此时就会涉及到每一个字符都可能是下一个子串的起点，如果使用循环，在找到一处不符合要求的子串时，还需要考虑如何回归到上一个起点，整体代码的复杂程度就会很高，所以对于分割问题也需要考虑使用回溯解决

力扣131.分割回文串

力扣131.分割回文串

问题描述：

Quote

给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。

示例 1：

C++
1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

C++
1
2
输入：s = "a"
输出：[["a"]]

思路分析：

首先考虑如何进行分割，知道分割的本质，利用该性质可以考虑思路：确定分割位置，判断分割位置前的字符串是否是回文串即可

以字符串aab为例，其决策树如下：

从上图可以发现，通过分割线就可以确定需要获取到的子字符串，在函数执行时只需要确定下一次分割线出现的位置即可。而两棵决策树本质区别就是分割线的位置不同

了解了基本思路后，接下来就是考虑如何编写代码，因为是递归，所以首先确定函数参数和返回值，函数的参数除了需要用到的字符串以外，还需要一个变量start表示分割线的起始位置，接着就是确定递归终止条件，对于本题来说，递归的终止条件就是当分割线已经到达原字符串末尾时就可以结束了，最后就是单层递归逻辑，本题的逻辑就是根据起始位置和终止位置（切割线的位置）切割出的字符串是否是回文串，如果是回文串就代表是个合法的子字符串，接着进行下一层，每一次递归结束后还需要进行回溯

注意，本题需要用到判断一个字符串是否是回文串，这个思路可以见字符串篇：力扣125.验证回文串

写法优化：

本题可以使用包装器和Lambda表达式将递归函数写在主函数内部

参考代码：

C++
 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
51
52
53
54
55
56
class Solution131_1
{
public:
    vector<vector<string>> ret;
    vector<string> temp;
    // 判断是否是回文串
    bool isPalindrome(const string &s)
    {
        for (int left = 0, right = s.size() - 1; left <= right;)
        {
            while (left <= s.size() - 1 && !isalnum(s[left]))
                left++;
            while (right >= 0 && !isalnum(s[right]))
                right--;

            if (left <= s.size() - 1 && right >= 0 && tolower(s[left]) != tolower(s[right]))
            {
                return false;
            }
            else
            {
                left++;
                right--;
            }
        }

        return true;
    }

    void backtracking(const string &s, int start)
    {
        if (start == s.size())
        {
            ret.push_back(temp);
            return;
        }

        for (int i = start; i < s.size(); i++)
        {
            string path = s.substr(start, i - start + 1);
            if (isPalindrome(path))
                temp.push_back(path);
            else
                continue;
            backtracking(s, i + 1);
            temp.pop_back();
        }
    }

    vector<vector<string>> partition(string s)
    {
        backtracking(s, 0);

        return ret;
    }
};
C++
 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
51
52
53
54
55
56
57
58
59
class Solution131_2
{
public:
    vector<vector<string>> ret;
    vector<string> path;

    vector<vector<string>> partition(string s)
    {
        function<bool(const string &)> isPalindrome =
                [&](const string &str) -> bool
        {
            for (int left = 0, right = str.size() - 1; left <= right;)
            {
                while (left <= str.size() - 1 && !isalnum(str[left]))
                    left++;
                while (right >= 0 && !isalnum(str[right]))
                    right--;

                if (left <= str.size() - 1 && right >= 0 &&
                    tolower(str[left]) != tolower(str[right]))
                {
                    return false;
                }
                else
                {
                    left++;
                    right--;
                }
            }

            return true;
        };
        function<void(int)> backtracking =
                [&](int start) -> void
        {
            if (start == s.size())
            {
                ret.push_back(path);
                return;
            }

            for (int i = start; i < s.size(); i++)
            {
                string str = s.substr(start, i - start + 1);
                if (isPalindrome(str))
                    path.push_back(str);
                else
                    continue;

                backtracking(i + 1);
                path.pop_back();
            }
        };

        backtracking(0);

        return ret;
    }
};

力扣93.复原IP地址

力扣93.复原IP地址

问题描述：

Quote

有效IP地址正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0），整数之间用.分隔。

例如："0.1.2.201"和"192.168.1.1"是有效IP地址，但是0.011.255.245、192.168.1.312和192.168@1.1是无效IP地址。 给定一个只包含数字的字符串s，用以表示一个IP地址，返回所有可能的有效IP地址，这些地址可以通过在s中插入.来形成。你不能重新排序或删除s中的任何数字。你可以按任何顺序返回答案。

示例 1：

C++
1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

C++
1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

C++
1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

思路分析：

本题的基本思路与分割字符串类似，只是要额外判断是否是合法的IP地址。本题需要注意，判断是否是合法IP需要对每一部分都要判断，也就是说，只要有一个区间不合法就可以不需要再继续向下寻找

参考代码：

C++
 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
51
52
53
54
55
56
57
58
59
class Solution93
{
private:
    vector<string> result; // 记录结果
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量
    void backtracking(string &s, int startIndex, int pointNum)
    {
        if (pointNum == 3)
        {
            // 逗点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1))
                result.push_back(s);
            return;
        }
        for (int i = startIndex; i < s.size(); i++)
        {
            if (isValid(s, startIndex, i))
            {
                // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1, '.'); // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--; // 回溯
                s.erase(s.begin() + i + 1); // 回溯删掉逗点
            }
            else
                break; // 不合法，直接结束本层循环
        }
    }

    // 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
    bool isValid(const string &s, int start, int end)
    {
        if (start > end)
            return false;
        if (s[start] == '0' && start != end) // 0开头的数字不合法
            return false;
        int num = 0;
        for (int i = start; i <= end; i++)
        {
            num = num * 10 + (s[i] - '0');
            if (num > 255) // 如果大于255了不合法
                return false;
        }

        return true;
    }

public:
    vector<string> restoreIpAddresses(string s)
    {
        result.clear();
        if (s.size() < 4 || s.size() > 12)
            return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

子集问题

子集问题也属于组合问题，但是与前面组合问题不同的是，子集的结果集长度不定，往小了说，空集是任意集合的子集，往大了说，全集也是当前集合的子集，所以子集问题最大的特点就是更新结果的位置不定，其他的思路和组合问题是一样的

力扣78.子集

力扣78.子集

Quote

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

C++
1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

C++
1
2
输入：nums = [0]
输出：[[],[0]]

思路分析：

前面已经介绍了子集问题的特点，根据这个特点就可以推出，子集问题中每一次的递归都会存在需要的结果，而前面的组合只有在满足条件时才会可能有需要的结果，所以子集问题收集结果时需要每一次递归就收集一次。另外，因为组合问题注定会有下标控制防止重复，而本题的子集问题不需要考虑特定条件终止递归，所以本题的递归也可以不显式写递归终止条件，其逻辑已经在循环中体现

参考代码：

C++
 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
class Solution78
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    void backtracking(const vector<int> &nums, int start)
    {
        ret.push_back(path);
        // 可以不需要单独写递归结束条件，start赋值给i时会在下面的for循环判断从而结束递归
        // if(start == nums.size())
        //     return;

        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 ret;
    }
};

力扣90.子集Ⅱ

力扣90.子集Ⅱ

问题描述：

Quote

给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

示例 1：

C++
1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

C++
1
2
输入：nums = [0]
输出：[[],[0]]

思路分析：

本题的思路就是子集题目的思路+组合总和Ⅱ中的树层去重即可

参考代码：

C++
 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
class Solution90
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {
        vector<int> used(nums.size(), 0);
        sort(nums.begin(), nums.end());

        function<void(int)> backtracking = [&](int start)-> void
        {
            ret.push_back(path);

            for (int i = start; i < nums.size(); i++)
            {
                // 树层去重
                if (i - 1 >= 0 && nums[i] == nums[i - 1] && !used[i - 1])
                    continue;

                path.push_back(nums[i]);
                used[i] = 1;
                backtracking(i + 1);
                path.pop_back();
                used[i] = 0;
            }
        };

        backtracking(0);

        return ret;
    }
};

力扣491.非递减子序列

力扣491.非递减子序列

问题描述：

Quote

给你一个整数数组nums，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

C++
1
2
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

C++
1
2
输入：nums = [4,4,3,2,1]
输出：[[4,4]]

思路分析：

本题也是属于子集问题，但是本题需要确保每一种结果中的元素个数都是大于等于2且呈现递增的，解题思路还是子集问题的思路，但是需要考虑不同的去重方式，本题使用unordered_set进行去重，只需要确保当前数值比当前组合的最后一个元素大即可插入到当前组合中，本题不推荐使用used数组进行去重，因为used数组需要用到排序的条件，但是本题不能进行排序，一旦排序就会打乱原有的元素顺序从而出现不存在的非递减序列

思路优化：

因为本题数据范围是[-100, 100]，所以可以考虑直接使用数组进行直接定址，但是需要注意，因为存在负数，所以考虑整体对插入的数字加100，映射到[0, 200]范围的空间

思路拓展：

本题使用到了回溯问题中第二种去重方式，即使用unordered_set，之前使用used数组进行去重的题目也可以使用unordered_set进行去重，道理都是一样的，只是思路上有一点不同

参考代码：

C++
 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
class Solution491_1
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    vector<vector<int>> findSubsequences(vector<int> &nums)
    {
        function<void(int)> backtracking = [&](int start)-> void
        {
            if (path.size() >= 2)
                ret.push_back(path);

            // 使用set记录当前层的数值，便于后续判断是否重复使用数值相同的数字
            unordered_set<int> uset;
            for (int i = start; i < nums.size(); i++)
            {
                // 树层去重
                if (!path.empty() && nums[i] < path.back() || uset.count(nums[i]))
                    continue;

                path.push_back(nums[i]);
                // 不需要对uset进行回溯，因为每一次递归都是新的uset
                uset.insert(nums[i]);
                backtracking(i + 1);
                path.pop_back();
            }
        };

        backtracking(0);

        return ret;
    }
};
C++
 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
class Solution491_2
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    vector<vector<int>> findSubsequences(vector<int> &nums)
    {
        function<void(int)> backtracking = [&](int start)-> void
        {
            if (path.size() >= 2)
                ret.push_back(path);

            // 使用set记录当前层的数值，便于后续判断是否重复使用数值相同的数字
            int uset[201] = {0};
            for (int i = start; i < nums.size(); i++)
            {
                // 树层去重
                if (!path.empty() && nums[i] < path.back() || uset[nums[i] + 100])
                    continue;

                path.push_back(nums[i]);
                // 不需要对uset进行回溯，因为每一次递归都是新的uset
                uset[nums[i] + 100] = 1;
                backtracking(i + 1);
                path.pop_back();
            }
        };

        backtracking(0);

        return ret;
    }
};

排列问题

排列问题主要涉及的还是全排列，因为排列需要注意每一种情况的元素顺序，所以在使用元素的方式上也会有所不同

力扣46.全排列

力扣46.全排列

问题描述：

Quote

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

C++
1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

C++
1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

C++
1
2
输入：nums = [1]
输出：[[1]]

思路分析：

排列与组合不同的是，排列讲究每一个结果中元素之间的顺序，一旦顺序不同，就是两种不同的情况，例如[1,2,3]和[1,3,2]，可以看到在排列中，尽管已经取过一个元素，下一次依旧还是从头开始找，并且还需要跳过已经选择的数字，所以可以考虑使用一个used数组用来标记取过的元素

参考代码：

C++
 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
class Solution46
{
public:
    vector<vector<int>> ret;
    vector<int> path;

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

        for (int i = 0; i < nums.size(); i++)
        {
            if (used[i])
                continue;

            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<bool> used(nums.size(), false);

        backtracking(nums, used);

        return ret;
    }
};

力扣47.全排列Ⅱ

力扣47.全排列Ⅱ

问题描述：

Quote

给定一个可包含重复数字的序列nums，按任意顺序 返回所有不重复的全排列。

示例 1：

C++
1
2
3
4
5
6
7
输入：nums = [1,1,2]
输出：
[
    [1,1,2],
    [1,2,1],
    [2,1,1]
]

示例 2：

C++
1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路分析：

本题就是全排列的思路+使用unordered_set对同层进行去重，但是因为本题数据范围很小，所以直接考虑用数组代替unordered_set。注意，如果使用used数组进行去重，此时会出现树层和树枝去重都可以解决的效果，具体原因以数组[1,1,1]分析，更推荐树层去重

参考代码：

C++
 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
class Solution47
{
public:
    vector<vector<int>> ret;
    vector<int> path;

    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        // 使用used标记是否已经使用过
        vector<bool> used(nums.size(), false);

        function < void() > backtracing = [&]()-> void
        {
            if (path.size() == nums.size())
            {
                ret.push_back(path);
                return;
            }

            // 记录当前层是否有相同元素已经被使用
            int isAppeared[21] = {0};

            for (int i = 0; i < nums.size(); i++)
            {
                if (used[i] || isAppeared[nums[i] + 10])
                    continue;

                path.push_back(nums[i]);
                used[i] = true;
                isAppeared[nums[i] + 10] = 1;
                backtracing();
                path.pop_back();
                used[i] = false;
            }
        };

        backtracing();

        return ret;
    }
};

棋盘问题

棋盘问题就是给定一个棋盘，根据某种规则去填充棋盘，通过回溯枚举出所有可能的填充情况，根据特定的规则排除其余的情况

力扣51.N皇后

力扣51.N皇后

问题描述：

Quote

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

N皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数n，返回所有不同的N皇后问题的解决方案。

每一种解法包含一个不同的N皇后问题的棋子放置方案，该方案中Q和.分别代表了皇后和空位。

示例 1：

C++
1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

C++
1
2
输入：n = 1
输出：[["Q"]]

思路分析：

本题主要的难度在于处理二维数组的回溯，通过画图分析+根据规则模拟即可解决本题。需要注意，本题题目并没有给定一个已经填充了对应符号的结构，所以需要额外开辟这个结构并填充对应的符号

参考代码：

C++
 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
51
52
53
54
55
56
57
58
class Solution51
{
public:
    vector<vector<string>> ret;
    vector<string> path;

    vector<vector<string>> solveNQueens(int n)
    {
        path = vector<string>(n, string(n, '.'));

        function < bool(int, int) > isValidQuene = [=](int row, int col)
        {
            // 因为每一次递归只会在当前行添加一个元素，所以同一行可以不同判断

            // 检查列
            for (int i = 0; i < row; i++)
                if (path[i][col] == 'Q')
                    return false;

            // 检查 45度角是否有皇后
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
                if (path[i][j] == 'Q')
                    return false;

            // 检查 135度角是否有皇后
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
                if (path[i][j] == 'Q')
                    return false;

            return true;
        };

        function < void(int) > backtracking = [&](int row)
        {
            // 当行数等于给定行时说明收到结果
            if (row == n)
            {
                ret.push_back(path);
                return;
            }

            // 遍历每一行，如果判断指定位置可以放置皇后就继续
            for (int i = 0; i < n; i++)
            {
                if (isValidQuene(row, i))
                {
                    path[row][i] = 'Q';
                    backtracking(row + 1);
                    path[row][i] = '.';
                }
            }
        };

        backtracking(0);

        return ret;
    }
};

力扣36.有效的数独

Note

本题并不涉及到回溯算法，但是本题可以通过判断是否是有效数独更好得理解数独，在下一题可以更轻松解决，本题的主要考点就是判断指定的数字是否满足数独的条件

问题描述：

Quote

请你判断一个9x9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

  1. 数字1-9在每一行只能出现一次。
  2. 数字1-9在每一列只能出现一次。
  3. 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 空白格用.表示。

示例 1：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

思路分析：

根据数独的条件暴力判断每个数字是否满足条件即可，是否需要用到回溯一定要根据题目判断，本题很明显固定了范围，从而可以确定嵌套两层循环比较每个位置即可

参考代码：

C++
 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
class Solution36
{
public:
    bool _isValidSudoku(vector<vector<char>> &board, int row, int col, char val)
    {
        // 判断行是否有重复
        for (int i = 0; i < 9; i++)
            if (i != col && board[row][i] == val)
                return false;

        // 判断列是否有重复
        for (int i = 0; i < 9; i++)
            if (i != row && board[i][col] == val)
                return false;

        // 判断一个格子中是否有重复
        int startRow = row / 3 * 3;
        int startCol = col / 3 * 3;

        for (int i = startRow; i < startRow + 3; i++)
            for (int j = startCol; j < startCol + 3; j++)
                if (i != (row % 3 + startRow) && j != (col % 3 + startCol) && board[i][j] == val)
                    return false;

        return true;
    }

    bool isValidSudoku(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] != '.')
                {
                    if (!_isValidSudoku(board, i, j, board[i][j]))
                    {
                        return false;
                    }
                }
            }
        }

        return true;
    }
};

力扣37.解数独

力扣37.解数独

问题描述：

Quote

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用.表示。

示例 1：

C++
1
2
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

思路分析：

本题就是一个二维回溯，根据规则枚举所有情况即可

参考代码：

C++
 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
51
52
53
54
55
56
57
58
class Solution37
{
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] == '.')
                {
                    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);
    }
};