Becomin' Charles

当我们遍历一棵二叉树的时候，根据遍历根节点的顺序的不同，可以有三种方法，前序遍历（Preorder），中序遍历（Inorder），后序遍历（Postorder）。分别对应着先访问根节点，在先左子树，然后访问根节点，接着右子树，或者最后访问根节点。这是很基本的数据结构知识点。今天的题目就是，给定一个二叉树的前序遍历和中序遍历结果，根据这个还原出二叉树。

其实前序遍历加中序遍历结果，就会唯一确定一棵二叉树。现在无非怎么操作的问题。我们可以从一个实例来分析这个：

1
2

preorder = [1, 2, 3, 4, 5, 6, 7, 8, 9]
inorder  = [3, 2, 4, 1, 6, 5, 8, 7, 9]

前序遍历的第一个节点是 1，则，在中序遍历中 3，2，4，[1]，6，5，8，7，9，就把序列分成了两份，前半段是左子树，后半段就是右子树。前序遍历的第二个节点是 2，则中序中的前半段 3，[2]，4，通过 2 把它又分成了两段，3，就是左子树，4，就是右子树。正好对应着前序遍历的第三个节点和第四个节点……

从这个顺序里，我们可以发现，前序遍历序列，我们只要按顺序逐个处理，而中序遍历的，我们不断分割左右两半，然后就是递归地处理这个过程。基于这个原理，我们可以用 Python 很简洁地写出这个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        n = len(preorder)
        pre = iter(preorder)

        def rec(left: int, right: int) -> TreeNode:
            if left >= right:
                return None
            r = next(pre)
            m = inorder.index(r, left, right)
            ltree = rec(left, m)
            rtree = rec(m + 1, right)
            return TreeNode(r, ltree, rtree)

        return rec(0, n)

我们声明一个函数 rec，代表 reconstruction（重建），用下标 left 和 right 来标记中序遍历序列的下标。因为前序遍历序列的分析，就是按顺序，所以我们生成一个迭代器来操作它，而下标 left 和 right，作用就是探测已到达叶子节点的标记。因为 index 这个方法的搜索范围是左闭右开区间的，所以我们对 left 和 right 的取值控制也是左闭右开的，这点需要注意。（为什么递归终止条件是 left >= right，因为是左闭右开，一个有效区间必须满足 left < right，区间里面才会有元素。）

看这个递归体里，我们用迭代器访问前序遍历的序列，迭代器不断往前移动，刚好把每个元素都访问了一遍。所以，整个算法的时间复杂度是 O(n)。

这个题目太简单了，我就不贴题目的原文了。意思是这样的，给你一个字符数组（字符串），然后，你要原地把这个数组的元素顺序反转。这道题目是非常平凡的，常规解法是使用双指针，头尾指针向中间夹逼，交换头尾指针指向的字符。

1
2
3
4
5
6
7

class Solution:
    def reverseString(self, s: List[str]) -> None:
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 

用 Python 写，会非常短小。时间复杂度是 O(n)，空间复杂度是 O(1)。

假如，让你为这个题目设计一个递归算法，你会怎么写呢？

方案一：假设我们掌握了一个把下标 [i, j] 范围内的字符顺序反转的方法。

那么对于这个题目来说，我们只要交换头尾两个字符，然后，用递归方法去计算中间剩余部分即可。

1
2
3
4
5
6
7

class Solution:
    def reverseString(self, s: List[str]) -> None:
        def reverse(i: int, j: int) -> None:
            if i < j:
                s[i], s[j] = s[j], s[i]
                reverse(i + 1, j - 1)
        reverse(0, len(s) - 1

这个方法和上面双指针其实如出一辙。

方案二：深度优先搜索，从当前位置探索最后一个字符，找到后，把最后一个字符放到正确位置，然后回溯。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def reverseString(self, s: List[str]) -> None:
        n = len(s)
        def dfs(i: int):
            if i == n:
                return
            c = s[i]
            dfs(i + 1)
            s[n - 1 - i] = c
        dfs(0

这里很有意思的一点，就是这个变量 c 可不可以不要？为什么？

你还能想出其他的递归设计方法么？欢迎给我留言。

这是今天的打卡题目，看标题，就知道这是系列题目，不过那不重要的。我们先来看看题目：

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

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

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

377. 组合总和IV <– 传送门

如果说，2～3 个月前，这种题我是不可能做出来的，不知道你信不信，现在总算是稍微觉得经过自己努力我也可以做出来了。看来这个还需要坚持和训练，就可以克服的。

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：
输入：4
输出：7
解释：7 = 4 * 3 / 2 + 1

示例 2：
输入：10
输出：12
解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

1006. 笨阶乘 <— 传送门

这道题目的意思是，计算每个数字的二进制表示里 1 的数量。其实，计算方法，也比较简单，就是写个循环，计算当前循环中的数字的 bit 位数。怎么计算一个数字的 bit 里的 1 的位数呢？

我想到的方法很简单，就是使用 “位与” 计算，一个整数，与 1 进行 & 运算，结果 1，说明最低位是 1，结果是 0，说明最低位是 0。然后，我们把这个数字往右移 1 位。重复这个过程，直到这个数字变为 0。就统计出了所有的 1 的数量。

然后我写出了这个算法：

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = []
        for i in range(num + 1):
            cnt = 0
            n = i
            while n > 0:
                cnt += n & 1
                n = n >> 1
            res.append(cnt)
        return res

这个算法的复杂度是多少呢？第一重循环是 n 次，第二重循环最多是 log2(n)次，随着数字的缩小，次数还会减少。具体就比较复杂了：[
O(\sum_{i=1}^{n}\log_2i)
]但是，原来题目里有个提示，就是，它问能不能用 O(n) 的算法计算出来。还提示了一句，算法的空间复杂度是 O(n)。你看，上面那个算法空间复杂度是 O(1) 的，没有用额外的空间。而现在明告诉你用 O(n)，其实就是说这题目可以使用递推法。现在 LC 的人流行叫动态规划，不过，我觉得动态规划在这个场景里没有递推法听起来更明白。不过写起来是一回事。

什么是递推法，就是现在第 n 个解，可以用 n 以前的解推理得到。算是动态规划的特殊情况吧。不像动态规划理解起来那么抽象。当然，我说得头头是道的，当时看到题目的时候，脑子是空白的，这个读者你知道就行了。

其实，从我写的那个式子里就看出一种来。比如我用了移位操作，往右移位，其实就是除以 2 的意思。举个例子，假如我现在循环到 5 这个数字，最低位是个 1，然后往右移，继续循环，往右移后其实数字变成了 2，而刚才，其实计算过 2 里面的比特数的，但是在我的算法里，右继续计算了，如果我们不计算，而是查表所得，这里就不用循环了。不是么？

算法可以改改：

1
2
3
4
5
6

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0]
        for i in range(1, num + 1):
            res.append(res[i >> 1] + (i & 1))
        return res

这个算法意思就是，先计算最低位的 1 的数量，然后高位部分，查表就行了。有了这个算法，官方题解的另一个算法就不难理解了。既然我们可以把最低位和上面部分分开计算。显然也可以把最高位和下面部分分开。不过，不像最低位这么直观。

我们可以把一个数字分解成，最高位 1 和剩余部分，举个例子：假如 5 二进制表示是 101，可以分解为 101 = 100 + 1，高位是 4，剩余的是 1，也就是 5 是 4 的比特数加上 1 的比特数。计算到 5 的时候，前面 1 和 4 肯定早就计算出来了。4 是什么呢？就是 5 前面最近的一个 2 的整数次幂。而怎么判断一个数字是 2 的整数次幂呢？i & (i - 1) == 0，想明白了么？

具体完整算法我就不写了。去看官方解答或者自己写也不难。

这是今天的打卡题，说实在做得我实在是心态崩坏，先来看看题目，我再来细说：

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

341. 扁平化嵌套列表迭代器 <– 传送门 力扣（LeetCode）

这道题虽然是简单，但是一看这复杂的操作，我就彻底懵逼了。每次将 n-1 个数字加一，最后要所有的数字相等。

这是太抽象的一个过程，脑海里自然联想到了滑块拼图之类的东西，或者覆盖问题，想得极其复杂，所以马上就不知道怎么做了。然后还草稿上画了很多，找这个问题的规律。找了半天也没找到。

暴力解，就是照着题目意思去做，我们想到的就是贪心法，每次挑出最大的一个，其他都加一，然后重复这个过程，直到所有的都相等为止。我想到了这个算法，但是一时半会儿也不能证明这个就是正确的操作法，因题目要求最小的次数。谁知道贪心法的次数是不是最小呢？

所以我就看答案了，果然这个就是最小，有时候做算法题看来也只能靠大胆了。这种根本不用证明的。。。猜一个就是了。猜错就跪了呗。

然后我看到官方题解竟然想出了四种解题方法，第一种就是我说的暴力法，照字面意思硬做。果然，超时，因为是 O(n^2) 的解法啊，肯定过不了。然后第二种是，每次不是加一了，而是直接加 最大值与最小值的 diff，这样可以少加几次。你这么说我当然明白，但是怎么证明这个加法和原来那个加法是等价的呢？也是靠猜就行了？这并不显然啊！！

第三种解法是什么动态规划，我就更懵逼了，根本不是人话好不好，我至今也没看懂。直到最后一个解法出现，我才明白过来。不过官方题解仍然不是用人话写的，我看了一个网友用人话写了，才终于恍然大悟，原来这么简单。

把 n-1 个数字都加一，其实相当于把最大值减 1，这样每次操作 n - 1 个数的抽象复杂情况，变成了一个极其简单的情况，每次挑最大值减 1，这就太简单了。最少肯定是所有值都减到最小值就可以了。太牛了，于是，就是很容易写出一个 O(n) 算法了。在一次遍历中，找到最小值，顺便找出所有数字的和，然后做个减法就完事了。

1
2
3
4
5
6
7

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        for i in reversed(range(1, len(nums))):
            res += nums[i] - nums[0]
        return res

最牛逼的 O(n) 算法我就不写了，大家自己写吧，上面这个是我写的 O(nlogn) 的算法，排序后，把所有数字和最小值的差求个和。

给我的启发：

1. 试试逆向思维，不要忘记这一点；
2. 虽然想明白后一点不难写，但是很多时候，题目难都在模型的转换上面，你看到的是假象。

今天的打卡题，是一道“困难”，先来看看题目：

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

115. 不同的子序列 <– 传送门

具体的例子，我都略去了，因为博客的排版比较弱，没法很好展示。其实，这道题目一看，就隐含了动态规划的气味，比如，求解的是个数，而不是具体的位置，第二，隐含了大量的穷举，才能进行的统计。

不过，如果你跟我一样小白的话，就会发现，你根本写不出状态转移的方程的，因为这个状态转移方程非常地不显然。

当然了，无论你想怎么去解决这道题目，首先还是要自己看懂题目。我们看看如何确定 t 在 s 中出现的次数。举个例子，假如 s = ababc，t = abc，那么很显然，t 在 s 出现了三次。然后我们来理一下，怎么统计。首先，我们把 t 的第一个字符 a，在 s 中标定，然后，是 b 标定，最后是 c，当 a 固定在第一个字符的时候，b 其实有两个选择。这两个选择的 b 都对应着唯一的 c，所以有两次，而 a，还有另一个选择，但是选那个 a 的时候，b，c 都只有唯一选择了，所以，总次数就是 3 次。

我上面描述的这个过程，就是一种最直观的统计策略。逐个标定 t 的每个字符，而且要穷尽每个字符的多个位置选择。这个就是一个比较明显的回溯过程。所以，很自然，我写出了回溯算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        self.res = 0
        self.dfs(s, t, 0)
        return self.res

    def dfs(self, s: str, t: str, p: int) -> None:
        if len(t) == 1:
            self.res += s[p:].count(t)
            return

        for i in range(p, len(s)):
            if s[i] == t[0]:
                self.dfs(s, t[1:], i + 1)

虽然是一道困难题，但是解法却很短小嘛，这个算法，每成功标定一个 t 的字符，就把 t 截短一截，然后继续向前扩展。这里有很低效的地方，比如每次截短 t，以及每次拷贝 s 之类的，容我偷个懒。

这个算法通过了 87% 的用例，说明，这是一个正确的算法，但是时间复杂度过高了。可以简单分析一下递归算法的时间复杂度，函数体内部，最坏情况循环大约是 len(s) - len(t) 次，而没深入一层，s 和 t 各减少了 1 （t 截短了 1 个字母，s 的下标后移了一个）。所以，然后把每层乘起来，综合复杂度是 O((m - 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

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        self.s, self.t = s, t
        self.m, self.n = len(s), len(t)
        self.mem = {}
        return self.dfs(0, 0)

    def dfs(self, p: int, q: int) -> int:
        if self.m - p < self.n - q:
            return 0

        # 缓存
        k = (p, q)
        v = self.mem.get(k, -1)
        if v > 0:
            return v
        
        if q == self.n - 1:
            v = self.s[p:].count(self.t[-1])
            self.mem[k] = v
            return v
        
        total = 0
        for i in range(p, self.m):
            if self.m - i >= self.n - q and self.s[i] == self.t[q]:
                total += self.dfs(i + 1, q + 1)
        
        self.mem[k] = total
        return total

然后，我优化出了这个算法：

1. 不在使用字符串作为参数，只是使用下标，避免了字符串拷贝
2. 改换了函数的返回值，使得方便去缓存
3. 引入了缓存来记录结果
4. 如果 s 长度小于 t 显然就不用继续搜索了，可以直接剪枝

这么多优化后，总共 62 个用例，过了 61 个，好消息是优化是有效的，效率提高了很多。坏消息是，仍然 TLE。这给我们最大的提示就是，非多项式时间的算法，无论怎么优化，在足够大的问题规模面前，就是无法有效运算。哈！

还是要使用递推方法，用动态规划来解，一个是不用递归，省去了栈的开销，另一个就是放弃了大量无效的搜索。但是写不出状态转移方程怎么办？不要急，仔细观察一下咱们优化后的算法。

为了避免拷贝字符串，我们用 p 和 q，记录了 s 和 t 的下标搜索位置，从上述算法里，我们能看到 dfs(p, q) 其实就是 dfs(i + 1, q + 1) 当 s[i] == t[q] 时，i 的取值范围是 [p, m)。这几乎就是状态转移方程了。

第一版状态转移方程：[
f(i, j) = \left {

\right.
]

现在这个方程基本上是没法写出代码来的，基本上是递归搜索方法的原本表达，一个是里面有个求和公式，就算写出来，算法的时间复杂度也是O(n^3)的，另一个就是，在 s[i] != t[j] 的时候，没有写出方程。这时候，我们就要耐心下来深入研究一下，怎么把这个状态方程给写完整了。

再来观察一下 dfs 的实现，在 for 循环里，套了一个 if，所以我们直接写出了 s[i] == t[j] 时候的情况，if 的 else 子句，代码里没写，其实就是 s[i] != t[j] 时的状态转移，我们发现，其实 else 的情况，就是跳过了这个下标，直接从下一个重复这个扫描过程了。相当于是调用了 dfs(i + 1, j) 了。这里可以品味一下。

然后在看怎么解决那个求和公式，其实解决起来也不难，就是咱们可以展开这个求和公式来看看：[

]

不知道这么解释，容易理解么？这里我们用了一个数列求和的小技巧，就是错位相减，然后得到了 f(i,j) 的递推公式，到此，我们就构造了我们的第二版状态转移方程：[
f(i, j) = \left {

\right.
]

有了状态转移公式，我们还要处理好边界条件，当 j = len(t) - 1 的时候，f(i, j) 的值，其实就是那个字符出现的次数。所以，我们可以把 i 从 0 到 len(s) 的值，初始化成在这个范围内搜索 t 的最后一个字符的出现次数。而实际上，更抽象地看，可以理解成，空串出现的次数。因为空串是任何串的子串，所以空串都会出现 1 次。当然，这个结论并不显然，这可能需要一些证明，我们可以这么猜测，如果是对的就万事大吉了。毕竟我们不是在做数学证明。

另外一个边界，就是递归代码里也用到了，就是 s 剩余的长度小于 t 剩余的长度时，就不用扫描了，显然结果是 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0
        dp = [[0] * len(t) for _ in range(len(s))]

        for i in range(len(s)):
            dp[i][len(t) - 1] = s[i:].count(t[-1])
        
        for i in range(len(s) - 2, -1, -1):
            for j in range(len(t) - 2, -1, -1):
                if s[i] == t[j] :
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
                else:
                    dp[i][j] = dp[i + 1][j]
        return dp[0][0]

我写出了这样的实现。7 - 8 行，可以用我说的更抽象的形式去替代，这样效率会更高一点。少了 len(s) 次的字符串统计行为。这个代码经测试是正确的。

总结，我通过这篇文章，从分析题目，到写出朴素的回溯算法，然后进行性能优化，发现了状态转移，并优化了状态转移方程，最终写出了动态规划算法。状态转移方程的物理意义，在优化过后已经变得比较模糊了，有时候强行去解释的话，，听起来很绕，而且一下子想看懂，恐怕也非常难。学习动态规划，不用去纠结这一点，不然真的会陷在里面。

这道题目，展示了一款二进制手表，然后问，给定点亮的灯的数量，计算可能展示出来的所有时间。这个题目，一看就知道可能要用回溯法了。

回溯法，其实就是穷举法的一种，只不过穷举得比较有章法而已，有时候我们说回溯法是深度优先搜索。回溯法的关键是，第一步，确认目标达成条件，作为回溯停止的点；第二步，找出状态空间，确认扩展下一步的方法；第三步，确认所有需要保存的状态；最后，写出递归算法。

对于这道手表的题目，题目要求点亮 num 盏灯，然后计算可能的时间数量。所以，我们可以把所有 num 盏灯都点亮，作为达成了目标的条件。第二，手表上，有代表小时的灯，1，2，4，8，四盏，以及代表分钟的灯1，2，4…… 等六盏灯，其实就相当于一共有 10 个位置，每次可以点亮一个。这么看，总状态空间，也就 2^10 个，就算都遍历了，也没多少……第三，我们要保存的状态，就是，点到第 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
35
36
37
38
39
40
41
42
43

class Solution:
    def __init__(self):
        self.result = []
        self.possible = [1,2,4,8,1,2,4,8,16,32]
        self.visited = [0] * 10

    def readBinaryWatch(self, num: int) -> List[str]:
        self.num = num
        self.dfs(0, 0)
        return self.result

    
    def dfs(self, step: int, start: int):
        if step == self.num:
            self.result.append( self.time_to_str() )
        else:
            for i in range( start, 10 ):
                self.visited[i] = 1
                if not self.valid():
                    self.visited[i] = 0
                    continue
                self.dfs(step + 1, i + 1)
                self.visited[i] = 0
    
    def valid(self) -> bool:
        h, m = self.cur_time()
        return h < 12 and m < 60
    
    def cur_time(self) -> ( int, int ):
        h = 0
        m = 0
        for i in range(10):
            if self.visited[i]:
                if i < 4:
                    h += self.possible[i]
                else:
                    m += self.possible[i]
        return h, m
    
    def time_to_str(self) -> str: 
        h, m = self.cur_time()
        return str(h) + ":" + ( "0" if m < 10 else "" ) + str(m)ç

上面的算法，用 visited 记住了每盏灯的亮灭情况。然后，把所有灯做了一个数组，逐盏去点亮，尝试每盏灯的亮灭组合。所有 num 盏灯点亮后，就算达成条件。剩下的就是剪枝了，对于不可能的时间（小时超过 11，分钟超过 59），可以直接跳过。

使用位图记录访问过的状态，是一个比较通用的做法，想不出来怎么记录状态的时候，这种“好记性不如烂笔头”的思维，很容易奏效。但是未必是最好的方法，不过好的方法总是需要灵光一现的。题解里，有个 C++ 的同学，提供了一个写法，他的不同在于，他用 dfs 方法的参数来记住状态，方法的参数也具有局部性，只在调用的时候有效，调用结束后，就天然可以回退。我们注意一下我们的做法，我们把 10 盏灯顺序排列了。从左往右去遍历，这个时候这个行为本身是有序的。而 visited 数组也是有序的，就是顺序这件事情我们记录了两次。其实其中一次是可以省略的。所以，这个同学用 hour 来记住小时，用 minute 来记住分钟，下标本身已经带有了顺序，就不用额外记录了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def __init__(self):
        self.result = []
        self.possible = [1,2,4,8,1,2,4,8,16,32]

    def readBinaryWatch(self, num: int) -> List[str]:
        self.num = num
        self.dfs(0, 0, 0, 0)
        return self.result

    
    def dfs(self, step: int, start: int, hour: int, minute: int):
        if step == self.num:
            time = str(hour) + ":" + ("0" if minute < 10 else "") + str(minute)
            self.result.append( time )
        else:
            for i in range( start, 10 ):
                if i < 4 and self.possible[i] + hour < 12:
                    self.dfs(step+1, i+1, hour + self.possible[i], minute)
                if i > 3 and self.possible[i] + minute < 60:
                    self.dfs(step+1, i+1, hour, minute + self.possible[i])

换种说法，上面第一种算法使用 visited 无法就是为了用于推算 hour 和 minute 的值，现在我直接记住 hour 和 minute 的时间就可以了，也做到可以正确回退，visited 就没用了。于是，写出了更简短的算法。不过在复杂度上是一样的。