找出 3 位偶数

难度: Easy

给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。

你需要找出所有满足下述条件且 互不相同 的整数：

该整数由 digits 中的三个元素按任意顺序 依次连接 组成。
该整数不含 前导零
该整数是一个偶数

例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。

将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。

示例 1：

输入：digits = [2,1,3,0]
输出：[102,120,130,132,210,230,302,310,312,320]
解释：
所有满足题目条件的整数都在输出数组中列出。 
注意，答案数组中不含有 奇数 或带 前导零 的整数。

示例 2：

输入：digits = [2,2,8,8,2]
输出：[222,228,282,288,822,828,882]
解释：
同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。 
在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。

示例 3：

输入：digits = [3,7,5]
输出：[]
解释：
使用给定的 digits 无法构造偶数。

提示：

3 <= digits.length <= 100
0 <= digits[i] <= 9

Submission

运行时间: 73 ms

内存: 16.6 MB

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        def huisuo(num,k,digits):
            if k == 4:
                ans.append(num)
                return
            for i in range(len(digits)):
                if not i == 0 and digits[i] == digits[i-1]: #剪枝
                    continue
                if k == 1 and digits[i] == 0:   #百位
                    continue
                if k == 3 and digits[i] % 2 == 1: # 个位
                    continue
                huisuo(num*10 + digits[i],k+1,digits[:i]+digits[i+1:])
        ans = []
        digits.sort()
        huisuo(0,1,digits)
        return ans

Explain

该题解采用了回溯法来生成所有可能的三位数并验证其是否为偶数。首先，将数组排序以方便剪枝和去重。回溯函数 huisuo 从 1 开始计数，并根据当前位数的特定条件进行判断：若当前是百位且选中的数字为0，则跳过以避免前导零；若当前是个位且数字为奇数，则跳过以确保结果为偶数。通过递归调用 huisuo，依次在剩余的数字中选择下一个数字，直到形成一个完整的三位数后，将其添加到结果列表中。

时间复杂度: O(n^3)

空间复杂度: O(1)

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        def huisuo(num, k, digits):
            if k == 4:
                ans.append(num)
                return
            for i in range(len(digits)):
                if not i == 0 and digits[i] == digits[i-1]:  # 剪枝，避免重复元素造成的重复结果
                    continue
                if k == 1 and digits[i] == 0:  # 避免百位为0，造成前导零
                    continue
                if k == 3 and digits[i] % 2 == 1:  # 确保个位为偶数，形成偶数结果
                    continue
                huisuo(num * 10 + digits[i], k + 1, digits[:i] + digits[i + 1:])  # 选择下一数字，更新num和递归深度k
        ans = []
        digits.sort()  # 对数组进行排序，便于处理
        huisuo(0, 1, digits)  # 开始回溯，从num为0，深度1开始
        return ans

Explore

在回溯函数`huisuo`中，参数`k`表示当前的数字位数，从1开始计数（表示百位）。回溯函数递归调用时，每进入下一层，`k`的值都会增加1，分别代表百位、十位和个位。当`k`达到4时（即表示数字已有三位），函数会停止进一步的递归调用，并将当前生成的三位数添加到结果列表中，从而确保只生成三位数。

在回溯中跳过相同的元素是为了避免生成重复的三位数。由于输入数组`digits`在开始时已被排序，相同的数字会连续排列。通过检查当前元素与前一个元素是否相同，可以有效地跳过那些在同一层次可能导致重复结果的数字。这种方法简单且直接，能够在生成结果的过程中即时剪枝，减少不必要的计算和递归调用，从而提高算法效率。

在`huisuo`函数中，每当选择一个数字加入到当前生成的数中后，会在递归调用`huisuo`时，传递一个更新后的`digits`数组。这个更新是通过`digits[:i] + digits[i+1:]`实现的，即从数组中移除已选择的数字。这样，新的递归层中的`digits`数组不包含当前已被选用的数字，从而确保每个数字只被使用一次。

当`digits`数组中所有数字相同时，例如[8, 8, 8]，这种方法仍然有效，但只能生成一个结果，即888。由于所有数字相同，第一个剪枝条件会在除第一个数字外的所有递归调用中生效，导致只有第一个数字被重复使用三次，生成一个唯一的三位数。尽管这样的输入限制了结果的多样性，算法仍能正确处理并返回有效的结果。