P3803. 猜密码

解题思路

这道题本质上是一道无重复元素子集类型的回溯问题。 无非是在 经典题型、子集 的基础上多加了一个关于最小长度的判断。 套回溯模板即可解决问题。

关键处理

需要特别注意的是，由于题目要求输出的结果按照字典序从小到大输出，所以可以先对 nums 数组进行排序后再进行回溯。

思路展开 参考代码是子集型回溯的标准写法。先把输入的数字按字符串比较规则（String::compareTo，即字典序）从小到大排序，这一步同时保证了两件事：每个组合内部按字典序排列；组合之间按 DFS 先序生成的顺序天然就是字典序，无需再对结果排序。回溯函数带 startIdx 参数，每层只从 startIdx 往后选数字，选过的位置不会被回头再选，因此不会产生重复组合。与常规「只收叶子节点」的写法不同，这里的收集条件放在函数开头：只要当前 path 的长度已达到最小密码长度 n，就把 path 用逗号拼接后加入答案，也就是说所有长度不小于 n 的组合（而非固定长度）都会被收集。主函数里先做特判：若可选数字总数本身小于 n，任何组合都不可能达标，直接输出 None。

复杂度分析

• 设可选数字个数为 m。回溯枚举 m 个元素的全部子集，状态树节点总数为 O(2^m)；每命中一个长度不小于 n 的组合，用 String.join 拼接一次，代价与组合长度成正比，为 O(m)。总时间复杂度为 O(2^m × m)，瓶颈在子集枚举本身。
• 排序预处理为 O(m log m)，相对指数级枚举可忽略。
• 空间复杂度：递归深度与 path 最长为 O(m)，答案列表另占与输出总量同阶的空间。