[LeetCode] 每日一题 2094. 找出 3 位偶数（回溯法）
题目描述
给你一个整数数组 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 <= 1000 <= digits[i] <= 9
解题思路
这道题一开始我下意识地想用回溯法来解决，因此最先想到的做法是：先对 digits 进行排序，再在回溯过程中进行剪枝和去重。但很快我就意识到，这种做法虽然可行，但会让去重逻辑变得复杂且耗时，而且回溯完成后还要再进行一次排序，时间和空间开销都不太友好。
后来我发现了一个更优的解法：基于数字出现频率来构建三位数。我们可以先使用一个长度为 10 的数组记录每个数字出现的次数，然后从小到大枚举所有可能的三位偶数，利用计数数组判断当前数字是否可以由输入数组中的三个数字组成。
这种方法的好处是显而易见的：
天然有序，无需排序
每个合法的数字最多只会被构造一次，无需额外去重
剪枝更直接（比如个位数必须是偶数，百位不能是 0）
这正体现了思路转换的重要性 —— 有时候换一种角度思考问题，不但能让代码更简洁，也能让性能更优秀。
代码实现
class Solution {
public int[] findEvenNumbers(int[] digits) {
int[] count = new int[10];
for (int digit : digits) {
count[digit]++;
}
List<Integer> ans = new ArrayList<>();
backtrace(0, count, ans);
return ans.stream().mapToInt(Integer::intValue).toArray();
}
private void backtrace(int num, int[] count, List<Integer> ans) {
if (num >= 100) {
ans.add(num);
return;
}
for (int i = 0; i < 10; i++) {
if (count[i] == 0) {
continue;
}
if (num == 0 && i > 0 || num >= 1 && num <= 9 || num >= 10 && i % 2 == 0) {
count[i]--;
backtrace(num * 10 + i, count, ans);
count[i]++;
}
}
}
}复杂度分析
⏱ 时间复杂度：
O(1)，因为三位数最多只有900个（从100到999），遍历所有组合最多900次，判断每个数字是否可以由
digits中构造最多检查3次，因此整体是常数级别的
🧠 空间复杂度：
O(1)，只使用了一个固定大小的计数数组和最多保存900个结果的列表，不依赖输入大小
总结
这道题让我再次意识到：思维方式的不同直接影响代码的质量。回溯法不是一定要从排列组合的角度出发，也可以换个角度，从数字构造的角度出发，结合计数和剪枝，使问题变得更清晰可控。特别是在面对存在去重和排序问题的场景时，提前计数 + 顺序构造往往能带来意想不到的简化效果 💡
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。