1767. 寻找没有被执行的任务对（难度：困难）

题目描述

（通过次数2,575 | 提交次数3,212，通过率80.17%）

表：Tasks
+----------------+---------+
| Column Name    | Type    |
+----------------+---------+
| task_id        | int     |
| subtasks_count | int     |
+----------------+---------+
task_id 是这个表的主键。
task_id 表示的为主任务的id,每一个task_id被分为了多个子任务(subtasks)，subtasks_count表示为子任务的个数（n），它的值表示了子任务的索引从1到n。
本表保证2 <=subtasks_count<= 20。
表：Executed
+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| task_id       | int     |
| subtask_id    | int     |
+---------------+---------+
(task_id, subtask_id) 是这个表的主键。
每一行表示标记为task_id的主任务与标记为subtask_id的子任务被成功执行。
本表 保证 ，对于每一个task_id，subtask_id <= subtasks_count。
请试写一个SQL查询语句报告没有被执行的（主任务，子任务）对，即没有被执行的（task_id, subtask_id）。
以 任何顺序 返回即可。
查询结果格式如下。
示例 1：
输入：
Tasks 表:
+---------+----------------+
| task_id | subtasks_count |
+---------+----------------+
| 1       | 3              |
| 2       | 2              |
| 3       | 4              |
+---------+----------------+
Executed 表:
+---------+------------+
| task_id | subtask_id |
+---------+------------+
| 1       | 2          |
| 3       | 1          |
| 3       | 2          |
| 3       | 3          |
| 3       | 4          |
+---------+------------+
输出：
+---------+------------+
| task_id | subtask_id |
+---------+------------+
| 1       | 1          |
| 1       | 3          |
| 2       | 1          |
| 2       | 2          |
+---------+------------+
解释：
Task 1 被分成了 3 subtasks (1, 2, 3)。只有 subtask 2 被成功执行, 所以我们返回 (1, 1) 和 (1, 3) 这两个主任务子任务对。
Task 2 被分成了 2 subtasks (1, 2)。没有一个subtask被成功执行, 因此我们返回(2, 1)和(2, 2)。
Task 3 被分成了 4 subtasks (1, 2, 3, 4)。所有的subtask都被成功执行，因此对于Task 3,我们不返回任何值。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-subtasks-that-did-not-execute

//测试数据
Create table If Not Exists Tasks (task_id int, subtasks_count int);
Create table If Not Exists Executed (task_id int, subtask_id int);

insert into Tasks (task_id, subtasks_count) values ('1', '3');
insert into Tasks (task_id, subtasks_count) values ('2', '2');
insert into Tasks (task_id, subtasks_count) values ('3', '4');

insert into Executed (task_id, subtask_id) values ('1', '2');
insert into Executed (task_id, subtask_id) values ('3', '1');
insert into Executed (task_id, subtask_id) values ('3', '2');
insert into Executed (task_id, subtask_id) values ('3', '3');
insert into Executed (task_id, subtask_id) values ('3', '4');

解题思路

虽然这是一道困难题，但从80%以上的通过率来看，其实并不难。

从题目描述来看，Tasks表保存了所有任务以及子任务的最大ID（子任务ID从1开始），Executed表保存了每个任务所有已经执行过的子任务。

而题目要求，计算出所有未被执行过的子任务。

那么，如果我们能够构建出一个任务下所有子任务的全集。然后剔除已经执行的子任务，剩下的就是未被执行过的子任务了。

因为Tasks表保存了子任务的最大ID，所以使用递归写法，可以构建出所有的子任务ID。

这里，构建所有子任务的全集有两条路径。

一条是从1出发，依次递增，直到子任务ID超过最大子任务ID；

另一条是从最大子任务出发，依次递减，直到子任务ID等于1；

下面的参考SQL使用的是第二种递归方式。

参考SQL

未特别说明的情况下，参考SQL为基于MySQL8.0实现。

with
recursive all_tasks as(
    select task_id,subtasks_count as subtask_id from Tasks
    union all
    select task_id,subtask_id - 1 as subtask_id from all_tasks where subtask_id > 1
)
select
    *
from all_tasks
where (task_id,subtask_id) not in (
    select task_id,subtask_id from Executed
);