参考《代码随想录》。

1.什么是回溯？

1.1 引言

回溯算法简单说来是通过递归进行遍历，他并不是一个高效的算法，因为整个遍历的过程是在穷举所有可能的结果。

在二叉树的OJ刷题博客中，就已经遇到了使用了回溯思路的题目。比如Leetcode 112 路径总和这道题，递归参数中的curSum就是利用回溯的的思路，从上层往下传的。

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
class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
	   // 这里体现回溯的思想，先将要遍历的下一层的值添加进去，然后再撤销操作。这样能让下一层先判断自己是否为叶子节点来正确停止递归。
        if (cur->left) { // 左
            count -= cur->left->val; // 递归，处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归，处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }

public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        return traversal(root, sum - root->val);
    }
};

1.2 什么问题用回溯能解决？

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

这些问题一般都涉及到了切割和组合，可以把一个大的集合通过一定的选择（当前层）再往下一层切割（缩小范围）来解决。通过这个思路整体看来，回溯法就很类似树形结构，与二叉树的递归遍历类似。

1.3 回溯法模板

在代码随想录中Carl大佬总结了一个回溯法的模板，这里引用如下。

既然回溯法用的大多都是递归，那么就需要明确递归的三部曲

  • 递归的参数
  • 递归的末端返回情况（终止条件）
  • 递归的单层操作逻辑

对于回溯法也是一样的

  • 回溯函数（递归函数）的参数
  • 回溯函数的末端返回情况（终止条件）
  • 回溯函数单层的选择（通常是遍历）

所以回溯法的代码模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void fallback(参数)
{
	if(终止条件){
		// 一般是存放结果到返回值数组中
        return;
	}
	// 单层逻辑
	for(循环逻辑，一般是树中节点孩子的数量就是当前层的处理数量)
	{
		// 处理节点
		fallback(参数) // 递归下一层
		// 撤销操作
	}
}

2.组合问题

下面的编号都是leetcode的题目号

77 组合问题

题目和思路

77. 组合

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1：
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：
输入：n = 1, k = 1
输出：[[1]]

这道题用循环暴力也不是不能写，但是一层K就需要多写一层循环，很难实现一个通用的暴力算法。所以需要用到递归的回溯算法来解决这道题。

这里直接借用一下代码随想录的图，每一层遍历就选择一个数字，再往下一层从这个值往后选择，直到长度为K或循环超出边界。

image-20240322105026000

根据这个思路，递归函数的参数如下

1
2
3
4
5
// n 和 k 是题目的参数
// start 是本层循环中开始循环的值（左边界）
// curV 保存当前递归的集合，这里不能采用引用传参，因为上一层会进行回溯撤销
// retV 保存最终的结果，使用引用传参；
void _combine(int n,int k,int start,vector<int> curV,vector<vector<int>>& retV)

递归的终止条件是curV中的元素个数等于K了（找到了一个符合条件的集合），就将curV插入到retV中。因为这里的curV传的不是引用，所以也不存在需要清空curV的操作。

因为我们是通过递归来进行curV的插入操作的，所以同一个元素不会在一个集合中被多次插入，不需要考虑去重的问题。

另外，还有一个隐含的终止条件是start大于n了，这在for循环的条件中就能体现出来，不需要单独处理。

1
for(int i = start;i<=n;i++)

每一层要做的事情就是从这个数字序列中选一个数出来插入当前数组curV，然后递归遍历下一层。调用完毕递归函数后，需要撤销当前选择的数，避免影响下一轮循环。

1
2
3
4
5
// 将当前值插入，然后递归进行下一次处理
curV.push_back(i);
// 这里应该从当前遍历值的下一个开始继续操作
_combine(n,k,i+1,curV,retV);
curV.pop_back(); // 回溯，撤销这一次操作

完整代码

代码如下

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
class Solution {
    
    // curV不需要加引用，因为是回溯算法
    void _combine(int n,int k,int start,vector<int> curV,vector<vector<int>>& retV)
    {
        // 数量足够，插入结果集
        if(curV.size() == k){
            retV.push_back(curV);
            return;
        }
        // 遍历进行回溯
        // for(int i = start;i<=n;i++) // 正常遍历

        // 剪枝操作，如果下一层剩下的都不足k个了，那就不需要继续了
        // 比如这一层是1 2 3 4，选择了3后只剩4，但k=4，此时完全不够长度，这次遍历是没有意义的
        // 计算n减去k还需要多少个，就能削减掉下一层不够用的情况
        // https://www.programmercarl.com/0077.%E7%BB%84%E5%90%88.html#%E6%80%9D%E8%B7%AF
        for(int i = start;i<=n -(k-curV.size()-1);i++)
        {
            // 将当前值插入，然后递归进行下一次处理
            curV.push_back(i);
            // 这里应该从当前遍历值的下一个开始继续操作
            _combine(n,k,i+1,curV,retV);
            curV.pop_back(); // 回溯，撤销这一次操作
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> retV;
        // 注意，题目给的范围是1到n
        _combine(n,k,1,vector<int>(),retV);
        return retV;
    }
};

image-20240322112408032

剪枝操作

这里对如下for循环的剪枝操作做说明

1
for(int i = start;i <= n-(k-curV.size()-1);i++)

题目要求的是k个数的组合，当前还需要的数字的个数是k-curV.size()，除去当前层以外（这里确定的是循环边界，进循环后就会处理当前层），还需要k-curV.size()-1个数字。

也就是说，我们需要保证递归处理的下一层还能有k-curV.size()-1个数字供处理，如果没有，那么下一层就不需要进去了，因为下一层是没有意义的递归，会浪费时间和压栈消耗。

这个思路可以参考下图，当N=4, K=3的时候，选择3时下一层只剩一个数字4了，肯定找不到符合条件的K=3长度的集合，所以在第一层遍历的时候，就可以直接跳过3和3之后的数字，不进行遍历回溯。

这个计算也比较简单，下一层还需要2个，那就N-2就行了；下一层还需要3个就是N-3（留了最后三个不用）。题目给的N是一个闭区间，不需要额外处理。

image-20240322103240017

反应到代码上，for循环的边界值就成了n-(k-curV.size()-1)，这样就能保证无论如何往下的递归一定能找到至少一个符合长度为K的集合。

在代码随想录网站上，描述的是用n - (k - path.size()) + 1这个边界进行剪枝，这个公式和上面我提供的公式是一致的，个人感觉我的那个公式的思路更好理解一些。

216 组合总和3

题目和思路

216. 组合总和 III

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

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

这道题和上一题基本一致，上一题给出的n是1到n的边界，这道题锁定了边界是1到9，额外多了一个要求是k个数的和要为n。

题目中还有个要求是每个数组最多使用一次，这也和我们回溯算法的思路一致，因为是从上层往下每次选用一个数进行递归的，并不会出现同一个数使用多次的情况。

代码模板

递归函数的参数和上一道题目一致，多了一个sum用于保存当前数组内元素的和

1
2
3
4
5
6
// n 和 k 是题目的参数
// start 是本层循环中开始循环的值（左边界）
// sum  当前curV数组内元素的和
// curV 保存当前递归的集合，这里不能采用引用传参，因为上一层会进行回溯撤销
// retV 保存最终的结果，使用引用传参；
void _combinationSum3(int k, int n,int start,int sum, vector<int> curV,vector<vector<int>>& retV )

递归的终止条件是curV中的元素大小等于k，然后判断成员的和是否为n，如果为n才插入返回值数组retV。

1
2
3
4
5
6
if(curV.size() == k){
    if(sum == n){
        retV.push_back(curV);
    }
    return;
}

一行的遍历也是一样的，将当前值插入数组，然后递归道下一层，并将当前层的操作撤销

1
2
3
4
5
6
7
8
9
10
11
for(int i = start;i<=9;i++)
      {
          // 单层操作
          curV.push_back(i);
          sum += i; 
          // 递归下一层
          _combinationSum3(k,n,i+1,sum,curV,retV);
          // 撤销
          curV.pop_back();
          sum -= i;
      }

上述代码可以进行简化，对sum的操作改为直接在传值的时候加一下i；

1
2
3
4
5
6
for(int i = start;i<=9;i++)
{
    curV.push_back(i);
    _combinationSum3(k,n,i+1,sum+i,curV,retV);
    curV.pop_back();
}

完整代码

完整代码如下

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
class Solution {
    
    void _combinationSum3(int k, int n,int start,int sum, vector<int> curV,vector<vector<int>>& retV ) { 
        if(curV.size() == k){
            if(sum == n){
                retV.push_back(curV);
            }
            return;
        }
        // 一次遍历
        for(int i = start;i<=9;i++)
        {
            curV.push_back(i);
            _combinationSum3(k,n,i+1,sum+i,curV,retV);
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> retV;
        _combinationSum3(k,n,1,0,vector<int>(),retV);
        return retV;
    }
};

image-20240322145222332

剪枝操作

和77题一样，上述的代码也能进行剪枝操作。分别针对的是k个数字和n的值

  • 下一层不够k-curV.size()个数字的时候就不需要递归下一层了。
  • 当前加上i之后已经超过sum了就不需要递归下一层了。

优化后的代码如下

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 Solution {
    
    void _combinationSum3(int k, int n,int start,int sum, vector<int> curV,vector<vector<int>>& retV ) { 
        if(curV.size() == k){
            if(sum == n){
                retV.push_back(curV);
            }
            return;
        }
        // 已经不符合条件，不进入循环
        if(sum > n){
            return;
        }
        // 一次遍历
        for(int i = start;i<=9 -(k-curV.size()-1);i++)
        {
            // 已经不符合条件，进入下一层
            if(sum + i > n){
                return; // 加i都已经超过n了，下一个数也没有必要遍历了
            }
         
            curV.push_back(i);
            _combinationSum3(k,n,i+1,sum+i,curV,retV);
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> retV;
        _combinationSum3(k,n,1,0,vector<int>(),retV);
        return retV;
    }
};

17 电话号码的数字组合

题目和思路

17. 电话号码的字母组合

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

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

image-20240322145712851

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]
  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

在早些年没有只能手机的时候，功能机一般都是九键的键盘（如上图所示），当时如果想在上面打字发短信，就需要按一个键来代表它下面的英文字母。比如你想打出字母h，就需要按4号键两次（第一次选中的是g，第二次是h）才能打出来。现在智能手机的九键键盘也是从这个设计思路衍生出来的，主要目的是增大屏幕上每个按键的大小，减少误触。

题外话：作为00后还算是用过这种东西，在我高中之前用的都是功能机，当时父母为了不让我玩游戏没给我买智能手机。不过这不影响我在功能机上玩贪吃蛇和五子棋，哈哈。

这道题就是让你算出来按下某个数字按键，他能打出什么字母组合的。

还是用回溯的思想，首先需要一个字符串数组来记录每一个按键对应的字母值。

1
2
3
4
5
6
7
8
9
10
11
12
vector<string> num2str = {
        "", /* 0 */
        "", /* 1 */
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };

对于这道题而言，每一次需要遍历的数组是对应数字的字符串，在这个字符串中选择一个字符后，往下一层遍历就行了。

image-20240322150726967

代码模板

首先是递归函数的参数，包括题目传入的字符串（理解为char的数组就行），当前遍历的下标（题目给出的字符串内的下标），当前的字符串（不能用引用传参），以及最终的返回值数组

1
void _letterCombinations(const string& digits,int index,string str,vector<string>& retV)

因为leetcode的c++题解都是有一个solution类的，所以retV这类返回值完全可以用一个类的成员变量来替代，可以节省一个递归的参数（虽然没有太大区别）

递归函数的终止条件是index大于digits的长度（下标越界）

1
2
3
4
if(index >= digits.size()){
    retV.push_back(str);
    return;
}

一层遍历中的处理如下，这里我单独判断处理了1（但题目给出的用例中其实不包含0和1），注意每一层遍历的字符串并不是digits，而是当前数字在键盘中对应的字母字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 通过ascii的计算得出当前数字，并找到curStr中映射的字符串
int num = digits[index] - '0';
if(num < 2) // 没有对应的
{
    retV.push_back(str);
    return;
}
// 一层的遍历
string& curStr = num2str[num];
for(int i = 0;i<curStr.size();i++){
    str.push_back(curStr[i]);
    _letterCombinations(digits,index+1,str,retV);
    str.pop_back();
}

完整代码

完整代码如下

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
class Solution {
    vector<string> num2str = {
        "", /* 0 */
        "", /* 1 */
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };


    void _letterCombinations(const string& digits,int index,string str,vector<string>& retV) {
        if(index >= digits.size()){
            retV.push_back(str);
            return;
        }
        // 通过ascii的计算得出当前数字，并找到curStr中映射的字符串
        int num = digits[index] - '0';
        if(num < 2) // 没有对应的
        {
            retV.push_back(str);
            return;
        }
        // 一层的遍历
        string& curStr = num2str[num];
        for(int i = 0;i<curStr.size();i++){
            str.push_back(curStr[i]);
            _letterCombinations(digits,index+1,str,retV);
            str.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        vector<string> retV;
        // 单独判断一下空字符串
        if(digits == ""){
            return retV;
        }

        _letterCombinations(digits,0,"",retV);
        return retV;
    }
};

image-20240322151941756

因为这道题每一次遍历的都不一定是同一个字符串，所以不存在剪枝操作，只能通过递归遍历完毕整个digits字符串。

39 组合总和

题目和思路

39. 组合总和

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

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

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

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

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

错误代码

这道题还是用回溯，和上面的组合问题的代码基本一致。

  • 和等于target的时候终止递归
  • 每一层都遍历数组，而且可以选择上一层已经选过的数。
  • 注意本题需要加的是数组元素的值，不是for循环里面的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
26
27
28
29
30
31
32
33
34
class Solution {
    void _combinationSum(vector<int>& candidates, int target, int sum,
                         vector<int> curV, vector<vector<int>>& retV) {
        // 值相等，插入
        if (sum == target) {
            retV.push_back(curV);
            return;
        }
        // 值已经大于了，不进入
        if (sum > target) {
            return;
        }
        // 每一层都是直接重新遍历整个数组
        for (int i = 0; i < candidates.size(); i++) {
            // 值已经大于了，不进入
            if (sum + candidates[i] > target) {
                continue; // 数组不一定是升序排列的，所以还需要往后走
            }
            curV.push_back(candidates[i]);
            _combinationSum(candidates, target, sum + candidates[i], curV, retV);
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> retV;
        if (candidates.size() == 0) {
            return retV;
        }
        _combinationSum(candidates, target, 0, vector<int>(), retV);
        return retV;
    }
};

哪怕是最简单的用例都错误了，肯定是有问题。

image-20240322153818632

问题出在哪儿呢？先不说会有很多无效的递归。以上图用例举例，如果这一层选择了3，下一层还是从最开始选取，那么就会出现3,2,...这种选取方式，但这个选取如果有结果的话，那么这个结果在当时选择从2开始时就已经得到过一次了。

注意题目要求如果一个结果集中数字出现的次数相同则视为一个，即[3,2,3]和[3,3,2]是同一个结果，这两个结果在返回值数组中只能出现一次。上图的输出中就出现了这种重复的结果集，不符合题目的条件。

正确代码

这就要求我们修改思路了，上面的代码最大的问题是没有进行切分，每一层都还是一个完整的数组。只需要按之前的思路对每一层进行切分，就能解决。

首先是递归函数的参数中需要多一个starti，用来记录上一层是从哪一个数开始的

1
2
3
void _combinationSum(vector<int>& candidates, int target, int sum,
                     	int starti,vector<int> curV, 
                     	vector<vector<int>>& retV)

for循环中也需要修改，因为题目允许同一个数被选用多次，这里我们直接从starti开始选则，并且传参给下一层的时候，也不需要对i进行加一操作（这样下一层可以选择和上层相同的数字，也不会往前选择），就是正确的思路了！

1
2
3
4
5
6
7
8
9
10
11
// 每一层都是直接重新遍历整个数组
for (int i = starti; i < candidates.size(); i++) {
    // 值已经大于了，不进入
    if (sum + candidates[i] > target) {
        continue; // 数组不一定是升序排列的，所以还需要往后走
    }
    curV.push_back(candidates[i]);
    _combinationSum(candidates, target, sum + candidates[i], i, curV,
                    retV);
    curV.pop_back();
}

最终完整的代码如下

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 Solution {
    void _combinationSum(vector<int>& candidates, int target, int sum,
                         int starti, vector<int> curV,
                         vector<vector<int>>& retV) {
        // 值相等，插入
        if (sum == target) {
            retV.push_back(curV);
            return;
        }
        // 值已经大于了，不进入
        if (sum > target) {
            return;
        }
        // 每一层都是直接重新遍历整个数组
        for (int i = starti; i < candidates.size(); i++) {
            // 值已经大于了，不进入
            if (sum + candidates[i] > target) {
                continue; // 数组不一定是升序排列的，所以还需要往后走
            }
            curV.push_back(candidates[i]);
            _combinationSum(candidates, target, sum + candidates[i], i, curV,
                            retV);
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> retV;
        if (candidates.size() == 0) {
            return retV;
        }
        _combinationSum(candidates, target, 0, 0, vector<int>(), retV);
        return retV;
    }
};

image-20240322154233646

这道题的剪枝思路在上述代码中已经体现了，即当前值已经大于target了，就不需要进入下一次递归了。注意这里要用continue而不是直接return，因为题目给定的数组不一定是升序排列的，如果直接return可能会错过结果集。

1
2
3
4
// 值已经大于了，不进入
if (sum + candidates[i] > target) {
	continue; // 数组不一定是升序排列的，所以还需要往后走
}

40 组合总和2

题目和思路

40. 组合总和 II

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

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

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

这道题并不能简单的从上道39题目修改而来，因为题目给出的candidates数组有不同，在39题中，candidates数组是没有重复元素的，但这道题中有重复元素，组合内也允许出现重复元素，但最终返回值内的组合不能重复，这就在去重方面给了我们更多的要求。

  • candidates数组中可能会有重复的元素；
  • 下一层不能再选取相同的元素（对应代码中的i需要加一后传入下一层）；
  • 返回值中的每个组合中可以出现重复元素；
  • 返回值中相同的组合不能出现多次；

一个比较简单的思路是用map或者set对最终的组合进行一次去重。在用例简单的时候，这样做不会超时，但用例多一点，再多来一次单独的去重操作就很容易超时了，所以最好是在遍历的时候就解决这个问题。

下图是代码随想录中的图（我自己画了老半天感觉画的很烂，还是借用一下老哥的图吧），主要的去重思路是，每一层选用的数需要进行去重，但下一层和上一层之间不需要去重。

比如第一层选用了第一个1后，第二层需要在[1,2]中选用，此时第二层依旧可以选用1；但是第一层往后的遍历中，数组的第二个1就不能选用了，应跳过。

image-20240324100837881

代码随想录中讲述到的思路是使用一个bool类型的used数组来实现这个功能，我觉得实在是麻烦且不是很好理解。

当然代码随想录后面还有一个比较简单的思路，也是我能想到的，即在for循环中直接判断当前数和上一个数是否相等来去重（跳过相等的情况）。对于回溯算法而言，每一次的for循环就是每一层了，符合题目需要的去重条件。

注意，使用这个办法需要将题目给出的数组进行排序（题目并没有保证给出的数组是有序的）。

完整代码

回溯递归的代码如下，在for循环中判断一下当前选用的元素和上一个是否相等就可以了。注意这里需要判断的是i>starti而不是i>0，因为i>starti才能保证去重是在同一层上，i>0虽然能保证不越界，但是下一层就无法选择和上一层的前一个相同的元素，不符合题目条件。

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
class Solution {
    void _combinationSum2(vector<int>& candidates, int target, int sum,
                          int starti, vector<int> curV,
                          vector<vector<int>>& retV) {
        // 值相等，插入
        if (sum == target) {
            retV.push_back(curV);
            return;
        }
        // 值已经大于了，不进入
        if (sum > target) {
            return;
        }
        // 每一层都是直接重新遍历整个数组
        for (int i = starti; i < candidates.size(); i++) {
            // 当前值和上一次相同，跳过
            // i > starti 保证是同一层的去重
            if(i > starti && candidates[i] == candidates[i-1]){
                continue;
            }
            // 值已经大于了，不进入
            if (sum + candidates[i] > target) {
                return; // 已经对数组进行排序了，可以直接返回
            }
            curV.push_back(candidates[i]);
            // 这道题就需要对i加一了，因为下一层不能选择下标相同的数字；
            _combinationSum2(candidates, target, sum + candidates[i], i + 1,
                             curV, retV);
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> retV;
        if (candidates.size() == 0) {
            return retV;
        }
        sort(candidates.begin(),candidates.end());
        _combinationSum2(candidates, target, 0, 0, vector<int>(), retV);
        return retV;
    }
};

image-20240324101552367

3.切割问题

切割问题的基本思路

  • 编写切割区间是否符合条件的判断函数
  • 确定切割区间终止条件（递归终止条件）
  • 确定单层循环如何指定切割区间。

131 分割回文串

题目和思路

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

回文串是从从左往右读和从右往左读都完全一致的字符串。

1
2
3
4
5
6
7
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：
输入：s = "a"
输出：[["a"]]

提示

1
2
1 <= s.length <= 16
s 仅由小写英文字母组成

思路依旧是用回溯，这是第一次遇到切割问题，我们主要是想办法通过下标区间“模拟”出来一个切割线。根据代码随想录提供的回溯模板，我们知道每一层都是一个for循环，此时就需要通过for循环的变量i来模拟一个切割线。

  • 当遍历到i时，认为s[i]和s[i+1]之间有一个切割线。

和前文的组合问题一样，我们也需要一个startIndex来标识每一层for的起点。本题需要跳过之前已经选过的子串。

  • 可以认为s[startIndex]和上一位字符之间有另外一个切割线
  • 这是上一层选中的切割线；
  • 刚开始的时候，startIndex为0，切割线在字符串开头；

for循环中什么时候需要递归到下一层呢？

  • 只有本层[startIndex,i]区域的字符串是一个回文串的时候，才需要递归下一层；
  • 否则本层已经不满足条件，递归到下一层也是没有意义的！
  • 本层区间已经是回文串，递归传入startIndex+1，从下一位开始选择新的回文子串；

递归的终止条件是什么？

  • 前文提到，“当遍历到i时，认为s[i]和s[i+1]之间有一个切割线。”

所以，当传入的startIndex为字符串size的时候，认为上一层的i已经走到了字符串末尾了，已经在字符串末尾处添加了一个切割线了，这时候就可以将结果插入数组了。

这里不需要做任何额外的判断，因为之前做的递归的判断条件已经决定了，能走到这里就说明所有子串已经满足回文条件。

1
2
3
4
if (startIndex >= s.size()) {
    retV.push_back(curV);
    return;
}

下面是一个切割的示意图，方便理解。

image.png

完整代码

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
class Solution {
    vector<vector<string>> retV; // 返回值数组
    vector<string> curV;         // 当前的回文子串

    void _partition(string s, int startIndex) {
        // 越界，说明上一层i已经是s.size()-1，此时分割线是在字符串末尾；
        // 已经是最后一个分割线了，说明找到了符合条件的切割（没找到是走不到这里来的）
        if (startIndex >= s.size()) {
            retV.push_back(curV);
            return;
        }
        // 遍历，将下标当作子串
        for (int i = startIndex; i < s.size(); i++) {
            // 如果是，将这里作为一个子串切割，递归到下一层找其他子串
            // 子串区间一直都是闭区间 [startIndex,i]
            // 此时i和i+1之间可以想象成有一个分割线
            if (isReverseString(s, startIndex, i)) {
	            // 插入当前选择的子串
                string temp = s.substr(startIndex, i - startIndex + 1);
                curV.push_back(temp);
                // 递归下一层
                // _partition(s, startIndex + 1); // 错误，i才是分割线位置
                _partition(s, i + 1);
                
                // 弹出当前选择的子串
                curV.pop_back(); // 回溯
            }
            // 如果不是，这一次的切割已经无效了，直接跳过
            else {
                // 注意不能break，因为后序可能还会有回文的情况
                // 比如ab和aba
                continue;
            }
        }
    }
    // 判断是否为回文子串，双指针法
    bool isReverseString(const string& str, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            if (str[i] != str[j]) {
                return false;
            }
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        _partition(s, 0);
        return retV;
    }
};

image.png

93 复原IP地址

https://leetcode.cn/problems/restore-ip-addresses/

题目和思路

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

1
例如："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
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"

提示：

1
2
1 <= s.length <= 20
s 仅由数字组成

这道题和上一题131的切割基本一致，只不过我们需要在虚拟的切割线的基础上做额外的处理，即把'.'字符当作切割线，插入到字符串中。因为题目最终返回的的字符串需要是带IP地址的'.'的，我们这样做就相当于提前处理了最终IP地址的字符串。

先来确定最终的递归终止条件吧，这里不再用startIndex大于size的判断方式，因为IP地址大概率是走不到这里就已经找到符合条件的子串了。我们应该利用IP地址中有3个'.'的特性来做递归的终止条件，即加了点的数量为3的时候，就已经不能继续执行本层了，需要退出了。

插入返回值之前，还需要判断最后一个点到字符串末尾的区间是否符合IP地址的条件。

1
2
3
4
5
6
7
if (pointNum == 3) {
    // 判断最后一部分是否符合ip的条件
    if (checkIpStr(s, startIndex, s.size() - 1)) {
        retV.push_back(s);
    }
    return;
}

IP地址的判断函数如下，保证区间的字符串对应的数字是0到255，且不能有前导0；

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
// 判断这个区间是否是合法的ip地址
   bool checkIpStr(const string& s, int start, int end) {
       // 区间合法（不能等于，start==end时是一个数字的情况）
       if (start > end) {
           return false;
       }
       // 以0开始的不合法（除非只有一个0）
       if (s[start] == '0' && start != end) {
           return false;
       }

       int sum = 0;
       for (int i = start; i <= end; i++) {
           // 不是数字，不符合
           if (s[i] < '0' || s[i] > '9') {
               return false;
           }
           // 加到sum里面
           sum = sum * 10 + (s[i] - '0');
           // 如果超过255，不符合
           if (sum > 255) {
               return false;
           }
       }
       return true;
   }

最终回溯函数的步骤如下：

  • 当遍历到i的时候，假设s[i]和s[i+1]之间有一个点；
  • 判断[startIndex,i]区间是否符合IP地址的规定（0到255）；
  • 符合条件，在i和i+1之间插入一个点；
  • 点的数量加一；
  • 递归下一层，其中startIndex应该传入i+2（跳过刚刚插入的点）；
  • 回溯，点的数量减一，删除刚刚添加的点；

完整代码

完整代码如下

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
66
class Solution {
    vector<string> retV;

    void _restoreIpAddresses(string s, int startIndex, int pointNum) {
        // IP地址需要打三个点，有三个点了之后就不需要继续for了
        if (pointNum == 3) {
            // 判断最后一部分是否符合ip的条件
            if (checkIpStr(s, startIndex, s.size() - 1)) {
                retV.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            // 判断[start,i]区间是否是合法的ip地址组成
            if (checkIpStr(s, startIndex, i)) {
                // 是，加点（注意insert是在选中位置之前插入）
                // 加点是为了方便最后直接插入返回值
                s.insert(s.begin() + i + 1, '.');
                pointNum++;
                // 这里加2是为了跳过插入的点，走到下一位
                _restoreIpAddresses(s, i + 2, pointNum);
                // 回溯本层操作
                pointNum--;
                s.erase(s.begin() + i + 1);
            }
            // 如果已经不符合条件了，说明这一层都不符合条件了
            // 比如515已经不符合条件了，再往后走更不符合（这一层符合条件的组合已经在之前走过了）
            else {
                break; // 跳出本层
            }
        }
    }

    // 判断这个区间是否是合法的ip地址
    bool checkIpStr(const string& s, int start, int end) {
        // 区间合法（不能等于，start==end时是一个数字的情况）
        if (start > end) {
            return false;
        }
        // 以0开始的不合法（除非只有一个0）
        if (s[start] == '0' && start != end) {
            return false;
        }

        int sum = 0;
        for (int i = start; i <= end; i++) {
            // 不是数字，不符合
            if (s[i] < '0' || s[i] > '9') {
                return false;
            }
            // 加到sum里面
            sum = sum * 10 + (s[i] - '0');
            // 如果超过255，不符合
            if (sum > 255) {
                return false;
            }
        }
        return true;
    }

public:
    vector<string> restoreIpAddresses(string s) {
        _restoreIpAddresses(s, 0, 0);
        return retV;
    }
};

image.png

4.子集/序列问题

78 子集

https://leetcode.cn/problems/subsets/description/

题目和思路

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

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

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

这道题的思路就不是很难了，属于是回溯算法的一个最基础的思路。

首先要根据题目需要的子集来确定什么时候插入返回值数组和递归的终止条件，最开始我的想法是单独处理每个元素构成的数组（比如[1],[2],[3]）和空数组[]；在递归终止条件中插入其他数组到返回值。

1
2
3
4
if(startIndex>=nums.size()){
 retV.push_back(curV);
    return;
}

但是这样会多出额外的一次遍历，虽然整体的时间复杂度没有变化，但多了一个遍历总归会浪费一些时间。

实际上也不需要这么麻烦，根据回溯算法的思路，其实第二层递归的时候，curV就是[1],[2],[3]这些由单个元素构成的数组了，也就是说，我们只要每一次递归调用函数的时候就把curV插入返回值，就能满足条件了！同时，第一次调用递归函数时，也正好会把空的curV给插入，空集也不需要额外处理了！

1
2
3
4
5
6
// 因为子集包括每一个数单独组成的数组和空数组，所以可以先直接把数组插入
// 第一次进入函数是插入空数组，第二层递归是插入每个数单独组成的数组
retV.push_back(curV);
if(startIndex>=nums.size()){
    return;
}

剩余的部分其实就是单层回溯了，题目要求不能有重复的子集（数组每个元素都不相同），所以下一层递归的时候，传给startIndex的是i+1，从下一位开始选择数插入数组就OK了。

完整代码

学过了前几题的回溯思路，这道题相对来说没有那么困难了。

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
class Solution {
    vector<vector<int>> retV;
    vector<int> curV;
    // 求子集的回溯函数
    void _subsets(vector<int>& nums,int startIndex)
    {
        // 因为子集包括每一个数单独组成的数组和空数组，所以可以先直接把数组插入
        // 第一次进入函数是插入空数组，第二层递归是插入每个数单独组成的数组
        retV.push_back(curV);
        if(startIndex>=nums.size()){
            return;
        }
        // 回溯的循环
        for(int i = startIndex;i<nums.size();i++){
            // 插入当前数
            curV.push_back(nums[i]);
            // 递归下一层，不能选择相同下标的数
            _subsets(nums,i+1);
            // 回溯当前操作
            curV.pop_back();
        }
    }

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

image.png

90 子集2

https://leetcode.cn/problems/subsets-ii/description/

题目和思路

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

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

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

这道题和78题的关系好比39和40题的关系一样，由78题的数组中不包括重复元素，变成了数组中有重复元素，且结果集不能有重复的子集。

如果还按照78题的思路来写，此时就会出现两个[1,2]子集的情况（一个是1和第一个2匹配的子集，另外一个是1和第二个2匹配的子集）。

实际上，每一层的处理都不能处理相同的数，包括进入下一层的递归也是。

1
2
3
4
5
6
[1,2,2,3]
当前 i = 1，选中第一个2
往下递归，可得到集合[2,2]、[2,3]、[2,2,3]

如果for循环不做去重，i = 2选中第二个2
往下递归，会重复得到集合[2,3]

这里的去重思路并不难实现，和40题的去重基本一致：在单层for中，如果上一位和当前位相等，则跳过当前位（重复了）。

1
2
3
if (i > startIndex && nums[i] == nums[i - 1]) {
	continue; // 跳过相同数
}

这样不仅解决了多个数的子集的重复问题，还解决了单个数的子集的重复问题，[1,2,2]在第一层for中，只会有1和第一个2进入下一层，最后一个2会被去重跳过，也就不会重复插入子集[2]。

完整代码

注意，这个判断上一位的去重思路是基于数组有序的，但题目并没有保证输入数组有序，所以调用递归函数之前，需要对数组排序。

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
class Solution {
    vector<vector<int>> retV;
    vector<int> curV;
    // 求子集的回溯函数
    void _subsetsWithDup(vector<int>& nums, int startIndex) {
        // 因为子集包括每一个数单独组成的数组和空数组，所以可以先直接把数组插入
        // 第一次进入函数是插入空数组，第二层递归是插入每个数单独组成的数组
        retV.push_back(curV);
        if (startIndex >= nums.size()) {
            return;
        }
        // 回溯的循环
        for (int i = startIndex; i < nums.size(); i++) {
            // 单层的去重
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue; // 跳过相同数
            }
            // 插入当前数
            curV.push_back(nums[i]);
            // 递归下一层
            _subsetsWithDup(nums, i + 1);
            // 回溯当前操作
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序
        _subsetsWithDup(nums, 0);
        return retV;
    }
};

image.png

491 非递减子序列

https://leetcode.cn/problems/non-decreasing-subsequences/description/

题目和思路

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

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

1
2
3
4
5
6
7
示例 1：
输入：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：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

1
2
1 <= nums.length <= 15
-100 <= nums[i] <= 100

首先注意这道题的要求，需要我们找到所有的递增子序列。这里包含了一个隐含的要求，即我们不可以对原数组进行重排序（否则找到的递增子序列不一定符合条件）。

  • 怎么判断当前找到的子序列是递增的？

通过startIndex来判断，我们需要保证当前层添加的数比上一层的数更大或相等，就是一个递增的子序列。第一层curV为空，不需要判断。

1
2
3
4
5
6
// 因为在for中每次都只会往curV插入一个数，所以可以直接判断
// 如果当前位小于startIndex-1，跳过
if (startIndex - 1 >= 0 && i > startIndex - 1 &&
	nums[i] < nums[startIndex - 1]) {
	continue;
}
  • 什么时候插入返回值？

题目需要的是所有递增的子序列。

此时既不能在越界终止条件中插入返回值，也不能直接在函数开始插入返回值。前者会导致结果集只包含叶子节点的子集（中途节点符合条件的子集未被加入），后者会导致只包含单个元素的子集被错误插入（题目要求子集必须至少有2个元素）。

正确的插入情况是curV的长度大于1的时候插入，这时候每一次递归都会把符合条件的子集插入其中。配合for循环内的去重逻辑避免重复子集被插入。

1
2
3
if (curV.size() > 1) {
          retV.push_back(curV);
      }

递归的终止条件依旧是startIndex大于数组长度

1
2
3
4
// 越界终止
if (startIndex >= nums.size()) {
    return;
}
  • 需要去重吗？

注意，本题也是需要去重的

1
2
3
4
5
6
[4,6,7,7]
第一层选择4，进入第二层，在[6,7,7]中选
如果不去重，就会出现两个[4,7]子集

第二层选择6，进入第三层，在[7,7]中选
如果不去重，就会出现两个[4,6,7]子集
  • 单层怎么去重？

之前的函数中，我们直接判断i不等于i-1来去重，但那是基于数组已经有序的情况下使用的了。

现在因为不能对原始数组做重排序，我们应该使用一个哈希表来对数组中元素去重。单层被选用过的元素不能再被使用。

1
2
3
4
5
6
7
8
9
// for循环之前定义去重集合
unordered_set<int> used; 

// for循环中，判断某个数是否已被使用过
if (used.count(nums[i]) != 0)
{
	continue;
}
used.insert(nums[i]);// 没有使用过则插入

此时的代码已经可以通过了。但针对本题，去重还有可优化之处：注意题目给的提示，数组中元素的大小区间是[-100,100]，这并不是一个很大的区间，我们完全可以使用一个201个元素的数组来替代unordered_set做去重的操作。

1
2
3
4
5
6
7
8
// for循环之前定义
vector<bool> usedArray(201, false); // num[i] + 100 作为下标

// for循环内直接判断对应下标位置即可
if (usedArray[nums[i] + 100] != false) {
	continue;
}
usedArray[nums[i] + 100] = true; // 标记已经使用过了

虽然unordered_set能提供O(1)级别的查找，但它并非严格的O(1)，同时插入的操作也会有更多的耗时。使用数组能保证不管是查询还是插入都只需要做1个操作。

针对这种哈希的情形，如果能确定数值的范围不大（比如本题或映射仅小写英文字母的情况），那么使用一个定长数组会优于使用哈希表。

完整代码

代码如下，本题主要是去重思路和其他题目不一样。

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 Solution {
    vector<vector<int>> retV;
    vector<int> curV;
    void _findSubsequences(vector<int>& nums, int startIndex) {
        // 题目要求子序列必须有两个元素
        if (curV.size() > 1) {
            retV.push_back(curV);
        }
        // 越界终止
        if (startIndex >= nums.size()) {
            return;
        }
        // 单层for中不能选择已经选过的数
        // unordered_set<int> used; // 去重集合
        // 因为题目给出了数字的区间是-100到100，可以直接用一个201长度的数组做哈希，提高效率
        vector<bool> usedArray(201, false); // num[i] + 100 作为下标
        // 单层for
        for (int i = startIndex; i < nums.size(); i++) {
            // 因为在for中每次都只会往curV插入一个数，所以可以直接判断
            // 如果当前位小于startIndex-1，跳过
            if (startIndex - 1 >= 0 && i > startIndex - 1 &&
                nums[i] < nums[startIndex - 1]) {
                continue;
            }
            // 单层for中不能选择已经选过的数
            // if (used.count(nums[i]) != 0)
            if (usedArray[nums[i] + 100] != false) {
                continue;
            }
            // 插入本层
            // used.insert(nums[i]);
            usedArray[nums[i] + 100] = true; // 标记已经使用过了
            curV.push_back(nums[i]);
            // 递归下一层
            _findSubsequences(nums, i + 1);
            // 回溯
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        _findSubsequences(nums, 0);
        return retV;
    }
};

image.png

698 划分为k个相等的子集

题目和思路

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

1
2
3
4
5
6
7
8
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

示例 2:
输入: nums = [1,2,3,4], k = 3
输出: false

这道题也算是用回溯可解的一个题目了。但是本题用例比较大，用回溯在不剪枝的情况下是会超时无法通过的。我们先说说回溯的基本思路。

首先，先计算题目给出的前置条件。因为需要划分为k个子集，且每个子集的和相等。那么这个和肯定是所有元素的和sum/k得到的值。同时，如果sum % k 不为0，则说明当前的数组不可能划分成功，这里算是第一个剪枝，直接返回false。

然后我们将划分子集换成往桶里放东西，桶的高度已经确定为sum/k了，我们只需要将数组中的每一个数找一个装得下的桶放进去，最终能将所有桶装满，即找到了符合条件的解，可以返回true。

根据这个思路，将回溯函数的参数定义如下。

1
2
3
4
5
// nums是原始数组
// bucket是每一个桶
// target是桶的高度
// index是当前选中的nums中的数字下标
bool _canPartitionKSubsets(vector<int>& nums, vector<int>& bucket, int target, index)

在每一个循环中，我们需要做的是将当前选中的数字nums[index]找到一个桶装下去。然后index+1递归到下一层，继续装桶。这里就能确定递归的终止条件为index越界。此时判断是否所有桶都装满了，只要有一个没有装满就返回false。

1
2
3
4
5
6
7
8
9
if(index >= nums.size()){
	// 判断所有桶是否都装满了
	for(auto&i:bucket){
		if(i!=target){
			return false;
		}
	}
	return true;
}

每一层的for循环就是在bucket中遍历，只要桶能装下这个数字，就试试把数字放进去，然后递归下一层。递归结束后撤回刚刚放入数字的操作。如果循环结束还没有找到解，则说明装不下，返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 开始每一层的操作，将当前index选择一个桶往里面装
for (int i = 0; i < bucket.size(); i++) {
    // 这个桶装不下，换一个桶
    if (bucket[i] + nums[index] > target) {
        continue;
    }
    // 装得下，将当前数装进去
    bucket[i] += nums[index];
    // 走下一个数字去，如果已经可以装好，则直接返回true
    if (_canPartitionKSubsets(nums, bucket, target, index + 1)) {
        return true;
    }
    // 当前数字装在i桶里面不可行，需要装另外一个桶
    // 回溯当前层的操作
    bucket[i] -= nums[index];
}
return false;

到这里，我们基本的回溯代码就已经写好了。但是直接提交会超时，需要进行剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool canPartitionKSubsets(vector<int>& nums, int k) {
    // 首先获取所有元素的和
    int sum = 0;
    for (auto& i : nums) {
        sum += i;
    }
    // 因为需要拆成k个，如果可以实现，最终的桶大小肯定是sum/k
    int target = sum / k;
    // 不能整除，说明无法实现，提前返回
    if (sum % k != 0) {
        return false;
    }
    vector<int> bucket(k, 0); // 初始化为0
    return _canPartitionKSubsets(nums, bucket, target, 0);
}

剪枝思路

首先是第一个剪枝，前文已经提到过，sum % k != 0的情况是肯定找不到解的，直接返回false。根据这个剪枝，在回溯函数中递归终止条件其实并不需要判断bucket数组是否已经全都满了。因为如果能走到index+1，那么当前肯定是一个正确解！

  • 因为当前的sum可以整除k，说明当前肯定有解；
  • 循环里面已经判断并排除了bucket[i] + nums[index] > target的情况，不可能会有bucket装多了；
  • 每一层的回溯只操作了一个数字，且放入了某一个bucket中；
  • 那么，只要回溯能走完全部nums数组中的数字，即代表所有数字都被放入了某一个bucket中，且没有任何一个bucket溢出了，那不就是都装满了吗？

此时越界直接返回true就可以啦，不需要再遍历一次bucket了。

1
2
3
if(index>=nums.size()){
	return true;
}

第二个剪枝涉及到排序，思路是如果前一个bucket和当前bucket的容量一致，那么跳过当前bucket（两个bucket都装了一样高度的东西，既然当前数字放不下上一个bucket，当前bucket肯定也放不下）。

1
2
3
4
// 前一个桶和当前桶的大小一样，说明当前的桶也装不下这个数字
if(i > 0 && bucket[i] == bucket[i-1]){
    continue;
}

为了更多的命中这个桶，我们需要在调用回溯函数之前，对nums数组进行排序。这样可以让bucket的数字分布更加均匀，可以更多的命中这个剪枝。这也是最重要的一个剪枝，不加上这个剪枝就一定会超时。

第三个剪枝是在题解中看到的，在回溯撤回操作之后，如果bucket[i]==0，说明原本是一个空桶，装了这个数字还是无法回溯出正确结果，那么当前数字哪儿都放不下，直接break（相当于返回false）。

1
2
3
4
5
6
7
// 当前数字装在i桶里面不可行，需要装另外一个桶
   // 回溯当前层的操作
   bucket[i] -= nums[index];
   // 如果当前bucket是0还装不下这个数字，说明其他桶也装不下，直接跳出
   if(bucket[i] == 0){
       break;
   }

这个剪枝我不是很理解，而且通过多次提交的测试，发现它似乎对耗时影响不大，暂且不管。

完整代码

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
66
67
68
class Solution {
    // 检查是不是每个桶都装满了
    bool bucketCheck(vector<int>& bucket, int target) {
        for (auto& i : bucket) {
            if (i != target) {
                return false;
            }
        }
        return true;
    }
    // bucket是每一个桶中的数字，target是每一个桶应该达到的值，index是当前选择的树
    bool _canPartitionKSubsets(vector<int>& nums, vector<int>& bucket, int target,
                               int index) {
        // index越界，判断是否符合条件，即是不是每个桶都装满了
        if (index >= nums.size()) {
            // 因为之前已经判断过sum%k != 0 的情况了，即所有数字肯定是有一个能成功放入的解的
            // 既然能走到这里，说明就已经找到了这个解，直接返回true就可以了，不需要额外的检查
            //return bucketCheck(bucket,target);
            return true;
        }

        // 开始每一层的操作，将当前index选择一个桶往里面装
        for (int i = 0; i < bucket.size(); i++) {
            // 这个桶装不下，换一个桶
            if (bucket[i] + nums[index] > target) {
                continue;
            }
            // 前一个桶和当前桶的大小一样，说明当前的桶也装不下这个数字
            if(i > 0 && bucket[i] == bucket[i-1]){
                continue;
            }
            // 装得下，将当前数装进去
            bucket[i] += nums[index];
            // 走下一个数字去，如果已经可以装好，则直接返回true
            if (_canPartitionKSubsets(nums, bucket, target, index + 1)) {
                return true;
            }
            // 当前数字装在i桶里面不可行，需要装另外一个桶
            // 回溯当前层的操作
            bucket[i] -= nums[index];
            // 如果当前bucket是0还装不下这个数字，说明其他桶也装不下，直接跳出
            if(bucket[i] == 0){
                break;
            }
        }
        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        // 首先获取所有元素的和
        int sum = 0;
        for (auto& i : nums) {
            sum += i;
        }
        // 因为需要拆成k个，如果可以实现，最终的桶大小肯定是sum/k
        int target = sum / k;
        // 不能整除，说明无法实现，提前返回
        if (sum % k != 0) {
            return false;
        }
        // 排序可以提高速度
        sort(nums.begin(), nums.end());

        vector<int> bucket(k, 0);
        return _canPartitionKSubsets(nums, bucket, target, 0);
    }
};

image.png

说来奇怪，我在题解中看到了一个C语言的写法，思路基本一模一样，但是耗时低的多。不太理解这里用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
bool reverse(int* nums, int numsSize, int k, int target, int* tmpArr, int index)
{
    if (index == numsSize) {//所有元素的枚举完了
        for (int i = 0; i < k; i++) {//判断是否每个桶都装满了
            if (tmpArr[i] != target) {
                return false;
            }
        }
        return true;
    }
    for (int i = 0; i < k; i++) {//枚举每一个桶
        if (tmpArr[i] + nums[index] > target) {//当前桶装不下了。下一个去
            continue;//剪枝
        }
        tmpArr[i] += nums[index];//装了
        if (reverse(nums, numsSize, k, target, tmpArr, index + 1)) {
            return true;//判断当前桶装了之后，下一个是否还能正常装好
        }
        tmpArr[i] -= nums[index];//下一个不能，说明这个球不是这个桶的，回溯
        //如果第一个球，在第一个桶里面装不了，那么因为所有桶都是一样的，
        //其他桶肯定也装不了，提前结束
        if (tmpArr[i] == 0) {//再剪枝
            break;
        }
    }
    return false;
}

bool canPartitionKSubsets(int* nums, int numsSize, int k){

    // 计算每个子集的和
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }

    if (sum % k != 0) {
        return false;
    }
    int target = sum / k;

    int tmpArr[k];
    memset(tmpArr, 0, sizeof(int) * k);

    return reverse(nums, numsSize, k, target, tmpArr, 0);
}


// 作者：小迅
// 链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solutions/1834523/-by-xun-ge-v-ij15/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

火柴拼正方形

题目和思路

https://leetcode.cn/problems/matchsticks-to-square/

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

image.png

这道题本质上是698划分子数组的另外一个问法，即k固定为4，问我们能不能将提供的数组划分为4个和相等的子数组。如果可以，就肯定能围城一个正方形。

所以，沿用上一题的代码就可以了。

完整代码

这里直接给出代码，具体思路参考本文上一题698。

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 Solution {
    bool _makesquare(vector<int>& matchsticks,vector<int>& bucket,int target,int index) {
        if(index>=matchsticks.size()){
            return true;
        }
        for(int i = 0;i<bucket.size();i++)
        {
            if(bucket[i] + matchsticks[index] > target){
                continue;
            }
            if(i > 0 && bucket[i]== bucket[i-1]){
                continue;
            }
            bucket[i] += matchsticks[index];
            if(_makesquare(matchsticks,bucket,target,index+1)){
                return true;
            }
            bucket[i] -= matchsticks[index];
        }
        return false;
    }
public:
    bool makesquare(vector<int>& matchsticks) {
        int sum = 0;
        for(auto&i:matchsticks){
            sum+=i;
        }
        // 不能整除4，不可能围城正方形
        if(sum % 4 !=0){
            return false;
        }
        int target = sum / 4;
        vector<int> bucket(4,0);
        sort(matchsticks.begin(),matchsticks.end());
        return _makesquare(matchsticks,bucket,target,0);
    }
};

image.png

5.排列问题

46 全排列

https://leetcode.cn/problems/permutations/

题目和思路

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

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

这道题和前文的子集问题都不同，这道题是希望我们将数组随便重新排列，并把所有可能重新排列的情况返回。

此时for循环就不需要使用startIndex了，因为每一次都需要从0开始遍历。比如当前选中了[1,2,3]中的2，还是需要从0开始遍历，加上1，再加上3；为此需要一个used数组来标记数组中哪一个元素已经被使用过了，跳过已经被使用的元素。

递归的终止条件也很简单，只要当前的curV和nums长度一致，就说明我们找到了一个全排列。

1
2
3
4
5
// 长度相等代表找到了一个全排列
if (curV.size() == nums.size()) {
    retV.push_back(curV);
    return;
}

本质上这道题就是一个暴力破解的过程，用回溯的思路模拟了一层循环。

完整代码

注意，我在主函数中使用resize初始化了used数组，因为需要保证刚开始的时候，所有下标都是false（未被使用）。

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
class Solution {
    vector<vector<int>> retV;
    vector<int> curV;
    vector<bool> used;
    // 因为全排列每次都需要从0开始，所以不需要startIndex
    void _permute(vector<int>& nums) {
        // 长度相等代表找到了一个全排列
        if (curV.size() == nums.size()) {
            retV.push_back(curV);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) {
                continue; // 跳过已经被选择了的
            }
            curV.push_back(nums[i]);
            used[i] = true;

            _permute(nums);

            used[i] = false;
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        used.resize(nums.size(), false); // 注意初始化
        _permute(nums);
        return retV;
    }
};

image.png

47 全排列2

https://leetcode.cn/problems/permutations-ii/

题目和思路

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

1
2
3
4
5
6
7
8
9
10
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
 
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

这道题和46题的区别在于给定数组内部元素可能重复，不过也不是第一次遇到这样的情况了。

以[1,1,2]为例，从第一个1开始回溯的时候，就可以得到[1,1,2]和[1,2,1]这两个排列。如果不去重，直接走到第二个1时，它还是会得到[1,1,2]和[1,2,1]这两个排列，此时排列重复！

因为本题并不在乎子集的顺序，所以我们直接通过排序，再加上if判断相邻节点的方式来去重，就可以了。

1
2
3
if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

加了这个代码发现，完全通过不了，输出结果为空，这是为什么呢？

image.png

以图中的用例[1,1,2]为例，这里无论什么情况都跳过了第二个1，第二层的时候也不会使用第二个1（这并不是我们预期的结果），这会导致curV永远无法达到nums的长度，也就没有结果被插入retV数组中。

正确的去重逻辑应该是：如果上一位被选用过且上一位的值和当前相同，那么就跳过当前位。在if判断中新增一个条件就可以了。

1
2
3
4
// 跳过相同的（前提是上一位已经被选择过了）
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

注意，这里需要判断的是used[i - 1] == false而不是为true的情况，因为在回溯过程中，我们会先把used[i]设置为true，然后又重置为false。在同一层里面，其实不会出现used[i-1]==true的情况（已经被回溯undo了）

既然不会出现used[i-1]==true的情况，为什么还需添加这个判断条件呢？原因前文已经提到过，如果删除这个判断，那么就会导致去重变成了多层之间都不会选择相同的数，这是不符合题目逻辑的！

在代码随想录上有关于这个去重逻辑更详细的解释：点我查看

当然，因为去重是基于同一层的，那么完全可以使用unordered_set来去重，效果也是一样的。不过使用set也不能去掉used数组，那还不如直接通过used数组来去重，效率更高。

image.png

注意，每一层递归都额外定义一个unordered_set会让整体空间复杂度由O(N)变成O(N^2)，所以除非必须的时候，不额外定义set才是更好的做法。

完整代码

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
class Solution {
    vector<vector<int>> retV;
    vector<int> curV;
    vector<bool> used;
    // 同样每一次都是从0开始，但是需要跳过单层已经被选择过的元素
    void _permuteUnique(vector<int>& nums) {
        // 长度相等代表找到了一个全排列
        if (curV.size() == nums.size()) {
            retV.push_back(curV);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // 跳过相同的（前提是同层上一位已经被选择过了）
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            // 正常情况下也需要跳过被选用了的
            if (used[i] == true) {
                continue;
            }
            curV.push_back(nums[i]);
            used[i] = true;

            _permuteUnique(nums);

            used[i] = false;
            curV.pop_back();
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        used.resize(nums.size(), false);
        sort(nums.begin(), nums.end());

        _permuteUnique(nums);
        return retV;
    }
};

image.png

6.其他问题

332 重新安排行程

https://leetcode.cn/problems/reconstruct-itinerary/description/

题目和思路

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

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

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

1
2
3
4
5
6
7
8
示例1：
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

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

提示

1
2
3
4
5
6
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

这道题其实更偏向于图论的深搜（还没学），但是它也可以通过回溯的思想来解决。

首先需要确定如何记录机票，最好的办法自然是用一个unordered_map来记录起始机场和目的机场的关系，且目的机场使用multiset而不是unordered_set，可以自然实现字典排序（set/map基于红黑树，是有序的）。使用multiset是为了避免有多张从A到B的机票的情况，此时目的地会重复出现。

1
2
// 起始机场,目的机场集合
unordered_map<string,multiset<string>> ticketsMap;

记录了之后，就可以实现回溯的单层遍历了。这里还需要一个计数器来整体记录当前选了多少个机票，机票数量够了就可以return了。

  • 参数startAp记录起始机场；
  • 遍历起始机场的目的地集合ticketsMap[startAp]，每次选择一个，继续往下递归；
    • 递归之前需要将选择的目的机场从set中删除，并插入retV返回值数组；
    • 递归结束之后将选择的目的机场重新插入set，并从retV返回值数组中删除；
  • 当遍历到某个机场的目的地集合为空的时候，说明走到了叶子节点，返回；
  • 当当前已经选择机票达到上限（注意每个机票必须且只能使用一次），返回；

这里就出现了一个问题：因为我们需要从set中删除数据，但删除的同时我们又需要继续遍历set，这便是一个经典的迭代器失效问题。因为set是基于红黑树的，当前节点被删除后，它就和其他节点没有链接关系了，迭代器无法继续往下走。不过我们可以先获取下一个迭代器的值，再删除，但那样对于for循环而言就有些麻烦了。

所以，我们可以将multiset改成另外一个map，用计数器来替代删除。当计数器为0的时候，可以认为这个机票已经不可用了（等价于被删除）

1
2
// <起始机场,<目的机场,票数>>
unordered_map<string,map<string,int>> ticketsMap;

用下面的循环对这个map进行初始化

1
2
3
for (auto& v : tickets) {
	ticketsMap[v[0]][v[1]]++;
}

这样，每一层for的时候，直接将对应票数减一即可。循环的时候跳过票数为0的机场即可。当一个机场的所有目的地机票都为0，则说明这个机场不能继续往下飞了。

错误代码

根据上面的思路，可以写出这样的第一版代码。注意代码中范围循环中auto一定要写引用auto&，因为我们需要通过p.second直接修改ticket的计数器。

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
class Solution {
    vector<string> retV;
    // 判断是否所有机票都用完了
    bool checkTicketsEmpty(map<string, int>& tickets) {
        for (auto& p : tickets) {
            if (p.second != 0) {
                return false;
            }
        }
        return true;
    }

    // 回溯法，每一次都找一个机场走，注意起点机场是JFK
    // ticketSum是总共的机票数量，ticketNum是当前已经被使用过的机票数量
    void _findItinerary(unordered_map<string, map<string, int>>& ticketsMap,
                        const int ticketsSum, int ticketsNum,
                        const string& startAp) {
        // 如果ticket被用完了，也可以返回
        if (ticketsNum == ticketsSum) {
            return;
        }
        // 如果map里面对应的目的机场机票都用完了，这一层没有办法往下走了
        if (checkTicketsEmpty(ticketsMap[startAp])) {
            return;
        }

        // 如果不是，随机选择一个机场往下走
        for (auto& p : ticketsMap[startAp]) {
            // 跳过已经选择了的机场
            if (p.second == 0) {
                continue;
            }
            // 没有选择过，可以走
            retV.push_back(p.first);
            p.second--;   // 机票数量减一
            ticketsNum++; // 已选机票数量加一
            cout << startAp << "->" << p.first << ":" << p.second
                 << " num:" << ticketsNum << endl;
            _findItinerary(ticketsMap, ticketsSum, ticketsNum, p.first);
            // 回溯操作
            p.second++;
            ticketsNum--;
            retV.pop_back();
        }
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 存放<起点机场,<目的机场,票数>>
        // 两个机场之间单向只会有一个票，所以不需要用multimap
        unordered_map<string, map<string, int>> ticketsMap;
        for (auto& v : tickets) {
            ticketsMap[v[0]][v[1]]++;
        }
        // 因为是从JFK开始的，所以需要先把第一个值插入
        retV.push_back("JFK");
        _findItinerary(ticketsMap, tickets.size(), 0, "JFK");
        return retV;
    }
};

但是这一版代码有问题，会发现结果集里面只有JFK被插入了

image.png

这是因为当前用例中，for循环内并没有进行条件判断，这就导致retV一直在被插入->递归->删除，最终retV里面的值还是空的。

添加一个cout打印，可以看到如下输出，其中ticketsNum已经打印到4了，说明我们期待的结果起始已经出现了，但因为回溯的pop_back又被删除了。

1
2
3
4
JFK->MUC:0 num:1
MUC->LHR:0 num:2
LHR->SFO:0 num:3
SFO->SJC:0 num:4

所以，我们需要在for循环中添加一个判断，当当前递归的返回值retV已经符合条件的时候，直接跳过pop_back回溯步骤，提前返回。

1
2
3
4
5
_findItinerary(ticketsMap, ticketsSum, ticketsNum, p.first);
         // 符合条件了，直接跳出
         if (retV.size() == ticketsSum) {
             return;
         }

这里的判断是错误的，因为传入的ticketsSum是机票的总数量，而retV中的结果集是存放路途中经过地点的，经过的地点应该比机票数量多一张！

1
2
3
4
// 符合条件了，直接跳出，地点比机票数量多一个
if (retV.size() == ticketsSum+1) {
    return;
}

完整代码

下面是正确的代码

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
class Solution {
    vector<string> retV;
    // 判断是否所有机票都用完了
    bool checkTicketsEmpty(map<string, int>& tickets) {
        for (auto& p : tickets) {
            if (p.second != 0) {
                return false;
            }
        }
        return true;
    }

    // 回溯法，每一次都找一个机场走，注意起点机场是JFK
    // ticketSum是总共的机票数量，ticketNum是当前已经被使用过的机票数量
    void _findItinerary(unordered_map<string, map<string, int>>& ticketsMap,
                        const int ticketsSum, int ticketsNum,
                        const string& startAp) {
        // 如果ticket被用完了，也可以返回
        if (ticketsNum == ticketsSum) {
            return;
        }
        // 如果map里面对应的目的机场机票都用完了，这一层没有办法往下走了
        if (checkTicketsEmpty(ticketsMap[startAp])) {
            return;
        }

        // 如果不是，随机选择一个机场往下走
        for (auto& p : ticketsMap[startAp]) {
            // 跳过已经选择了的机场
            if (p.second == 0) {
                continue;
            }
            // 没有选择过，可以走
            retV.push_back(p.first);
            p.second--;   // 机票数量减一
            ticketsNum++; // 已选机票数量加一
            // cout << startAp << "->" << p.first << ":" << p.second
            //      << " num:" << ticketsNum << endl;
            _findItinerary(ticketsMap, ticketsSum, ticketsNum, p.first);
            // 符合条件了，直接跳出，地点比机票数量多一个
            if (retV.size() == ticketsSum + 1) {
                return;
            }
            // 回溯操作
            p.second++;
            ticketsNum--;
            retV.pop_back();
        }
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 存放<起点机场,<目的机场,票数>>
        // 两个机场之间单向只会有一个票，所以不需要用multimap
        unordered_map<string, map<string, int>> ticketsMap;
        for (auto& v : tickets) {
            ticketsMap[v[0]][v[1]]++;
        }
        // 因为是从JFK开始的，所以需要先把第一个值插入
        retV.push_back("JFK");
        _findItinerary(ticketsMap, tickets.size(), 0, "JFK");
        return retV;
    }
};

image.png

这个代码还有可优化之处，比如checkTicketsEmpty函数中做的判断就没有意义了，因为for循环中本来也会判断票数是否为0。加上这个函数会让每一层递归的时间复杂度多一个O(N)。把它删除，代码也能通过。

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
class Solution {
    vector<string> retV;
    // 回溯法，每一次都找一个机场走，注意起点机场是JFK
    // ticketSum是总共的机票数量，ticketNum是当前已经被使用过的机票数量
    void _findItinerary(unordered_map<string, map<string, int>>& ticketsMap,
                        const int ticketsSum, int ticketsNum,
                        const string& startAp) {
        // 如果ticket被用完了，也可以返回
        if (ticketsNum == ticketsSum) {
            return;
        }
        // 如果不是，随机选择一个机场往下走
        for (auto& p : ticketsMap[startAp]) {
            // 跳过已经选择了的机场
            if (p.second == 0) {
                continue;
            }
            // 没有选择过，可以走
            retV.push_back(p.first);
            p.second--;   // 机票数量减一
            ticketsNum++; // 已选机票数量加一
			// 递归下一层
            _findItinerary(ticketsMap, ticketsSum, ticketsNum, p.first);
            // 符合条件了，直接跳出，地点数量比机票数量多一个
            if (retV.size() == ticketsSum + 1) {
                return;
            }
            // 回溯操作
            p.second++;
            ticketsNum--;
            retV.pop_back();
        }
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 存放<起点机场,<目的机场,票数>>
        // 两个机场之间单向只会有一个票，所以不需要用multimap
        unordered_map<string, map<string, int>> ticketsMap;
        for (auto& v : tickets) {
            ticketsMap[v[0]][v[1]]++;
        }
        // 因为是从JFK开始的，所以需要先把第一个值插入
        retV.push_back("JFK");
        _findItinerary(ticketsMap, tickets.size(), 0, "JFK");
        return retV;
    }
};

耗时也变短了（虽然这个耗时没有参考价值）。

image.png

代码随想录版本

下面的代码是《代码随想录》上的版本，大佬将递归函数的返回值改成了bool，以此来标识是否符合条件，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
29
30
31
class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
    if (result.size() == ticketNum + 1) {
        return true;
    }
    for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
        if (target.second > 0 ) { // 记录到达机场是否飞过了
            result.push_back(target.first);
            target.second--;
            if (backtracking(ticketNum, result)) return true;
            result.pop_back();
            target.second++;
        }
    }
    return false;
}
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const vector<string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

51 N皇后

https://leetcode.cn/problems/n-queens/description/

题目和思路

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

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

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

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

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

示例 2：
输入：n = 1
输出：[["Q"]]

这道题是回溯的经典题目：

  • 回溯每一层模拟每一列的遍历（横向）
  • 多层递归模拟每一行行的遍历（纵向）

整体的思路如下：

  • 每一层的for在当前行选择一个位置设置为Q
  • 判断该位置是否符合N皇后的条件
  • 符合，递归下一层，行号加一
  • 当行号等于N时，代表越界，插入结果集并终止递归。

主要是写出判断每一层是否符合皇后占位的代码，回溯的思路不难。

  • 皇后所在的行和列，斜线上都不能有其他皇后。

对于我们的回溯而言，因为每一层都是for在当前行选择一个作为皇后，所以同行不会有多个皇后，不需要判断当前行。

而回溯的每一层是模拟从上往下的纵向遍历，所以纵向上也只需要判断当前列在当前行之前是否有其他皇后（当前行之后都还没有被操作）。

其次就是斜线上的判断了，这里主要涉及到行和列下标如何操作，注意我们是从当前位置沿着斜线往上遍历

  • 135°斜线（右上到左下）：行号和列号每次都减一；
  • 45°斜线（左下到右上）：行号减一，列号加一；

如下就是判断当前位置是否可以放皇后的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool checkQueen(const vector<string>& curV, int n, int row, int col) {
    // 因为在回溯每一层的时候都只会选择一行进行处理，一行只会有一个Q，不需要遍历
    // 遍历列（这里小于row就行了，因为回溯才走到这里，更大的行是没有数据的）
    for (int i = 0; i < row; i++) {
        if (curV[i][col] == 'Q') {
            return false;
        }
    }
    // 遍历右边斜线（从右上到左下的斜线,135°）
    // 减一开始往回遍历
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (curV[i][j] == 'Q') {
            return false;
        }
    }
    // 遍历左边斜线，45°
    // 这里应该是列加一行减一，然后每一次都是行减一列加一
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (curV[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

错误代码

刚开始我写出了这样的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int col = 0; col < n; col++) {
          // 判断是否符合条件，不符合直接返回
          if (checkQueen(curV, n, row, col) == false) {
              continue; // 后面可能有符合条件的，不能return
          }
          curV[row][col] = 'Q'; // 假设为皇后
          row++;                // 下一行
          // 递归
          _solveNQueens(n, row, curV);
          // 回溯
          curV[row][col] = '.'; // 重置
          row--; 
      }

但是提交发现retV始终为空，想不明白为什么。最终加了一堆打印之后，发现了问题所在。如下所示，这是正确的一个结果集内的回溯过程，选中了(0,1)和(1,3)后，理论上(2,0)应该要被选中，但是(2,0)在判断中却因为(0,0)处是Q而退出了。打印出第0行的字符串，发现这里就有两个Q，很明显是第一波的操作没有被成功回溯。

1
2
3
4
5
6
7
8
9
good: 0 1
1 0
1 1
1 2
1 3
good: 1 3
2 0
2,0 exit here1： 0 0
string: QQ..

检查回溯部分的代码，会发现这两行有问题

1
2
3
// 回溯
curV[row][col] = '.'; // 重置
row--;

在调用递归函数之前，将row++了，此时回溯却先重置点再row–，问题就出现了：被重置的是下一行的col位置，和当前应该回溯的不是同一个位置！正确代码是先修复row再重置数组中的值！

1
2
3
4
// 回溯
row--; 
curV[row][col] = '.'; // 重置
// row--; // error，应该先减减再重置数组中的值

完整代码

正确的代码如下

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
class Solution {
    vector<vector<string>> retV;
    // n是皇后数量（同时也是棋盘的边长），row是行号
    void _solveNQueens(int n, int row, vector<string>& curV) {
        // 行号是下标，当下标row等于n的时候代表越界，找到了一个解
        if (n == row) {
            retV.push_back(curV);
            return;
        }
        // 列号，每一位都尝试使用
        for (int col = 0; col < n; col++) {
            // 判断是否符合条件，不符合直接返回
            if (checkQueen(curV, n, row, col) == false) {
                continue; // 后面可能有符合条件的，不能return
            }
            curV[row][col] = 'Q'; // 假设为皇后
            row++;                // 下一行
            // 递归
            _solveNQueens(n, row, curV);
            // 回溯
            row--;
            curV[row][col] = '.'; // 重置
            // row--; // error，应该先减减再重置数组中的值
        }
    }
    // 注意，每一次选择都需要做检查，判断同一行，同一列，斜线上是否有其他皇后
    // 入参是当前插入皇后的位置
    bool checkQueen(const vector<string>& curV, int n, int row, int col) {
        // 因为在回溯每一层的时候都只会选择一行进行处理，一行只会有一个Q，不需要遍历
        // 遍历列（这里小于row就行了，因为回溯才走到这里，更大的行是没有数据的）
        for (int i = 0; i < row; i++) {
            if (curV[i][col] == 'Q') {
                return false;
            }
        }
        // 遍历右边斜线（从右上到左下的斜线,135°）
        // 减一开始往回遍历
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (curV[i][j] == 'Q') {
                return false;
            }
        }
        // 遍历左边斜线，45°
        // 这里应该是列加一行减一，然后每一次都是行减一列加一
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (curV[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        if (n == 1) {
            retV.push_back(vector<string>{"Q"});
            return retV;
        }
        // 注意vector需要初始化，不然没有办法直接下标操作
        vector<string> curV(n, string(n, '.'));
        _solveNQueens(n, 0, curV);
        return retV;
    }
};

image.png