根据搜索结果我已经了解了 LeetCode 3533 的题目要求和解题思路。这是一个状态压缩动态规划问题核心思路是1. 排序先对 nums 排序这样按顺序搜索时第一个找到的可行解就是字典序最小的2. 预处理计算每个数字的位数和 10^len % k3. 状态压缩 DPdp[mask][mod] 表示已选数字集合为 mask当前拼接数模 k 为 mod 是否可行4. 路径重建通过记忆化搜索重建字典序最小的排列以下是 Rust 实现rustuse std::collections::HashMap;impl Solution {pub fn concatenated_divisibility(nums: Veci32, k: i32) - Veci32 {let n nums.len();let k k as usize;let mut nums nums;// 排序保证按顺序找第一个可行解就是字典序最小的nums.sort();// 预处理计算每个数字的位数和 10^len % klet mut lengths vec![0; n];let mut pow10_mod vec![0; n];for i in 0..n {let num nums[i] as usize;let len num.to_string().len();lengths[i] len;// 计算 10^len % klet mut pow 1usize;for _ in 0..len {pow (pow * 10) % k;}pow10_mod[i] pow;}// 状态压缩 DP// dp[mask][mod] true/false表示是否可行// 使用 HashMap 或二维数组这里用 VecVecOptionboollet mut memo vec![vec![None; k]; 1 n];// 先判断是否存在可行解if !Self::dfs(nums, pow10_mod, mut memo, k, 0, 0, n) {return vec![];}// 重建路径按排序后的顺序每次选第一个能导致可行解的数字let mut result Vec::with_capacity(n);let mut mask 0usize;let mut mod_val 0usize;for _ in 0..n {for i in 0..n {if (mask i) 1 1 {continue; // 已选过}let new_mod (mod_val * pow10_mod[i] nums[i] as usize) % k;let new_mask mask | (1 i);// 检查选这个数后是否仍能完成if Self::dfs(nums, pow10_mod, mut memo, k, new_mask, new_mod, n) {result.push(nums[i]);mask new_mask;mod_val new_mod;break;}}}result}fn dfs(nums: [i32],pow10_mod: [usize],memo: mut VecVecOptionbool,k: usize,mask: usize,mod_val: usize,n: usize,) - bool {// 所有数字都已选完if mask (1 n) - 1 {return mod_val 0;}// 记忆化if let Some(res) memo[mask][mod_val] {return res;}// 尝试每个未选的数字for i in 0..n {if (mask i) 1 1 {continue;}let new_mod (mod_val * pow10_mod[i] nums[i] as usize) % k;let new_mask mask | (1 i);if Self::dfs(nums, pow10_mod, memo, k, new_mask, new_mod, n) {memo[mask][mod_val] Some(true);return true;}}memo[mask][mod_val] Some(false);false}}关键思路说明1. 排序保证字典序先对 nums 排序在 DFS 和重建路径时都按升序尝试这样第一个找到的可行解就是字典序最小的排列。2. 模运算拼接拼接 a 和 b 的数学表示为 a * 10^len(b) b。在模 k 意义下如果当前余数为 mod拼接数字 nums[i]长度为 len后的新余数为new_mod (mod * (10^len % k) nums[i]) % k3. 状态压缩用 mask二进制位表示已选数字集合dp[mask][mod] 记录该状态是否可行避免重复计算。4. 路径重建先通过 DFS 填充记忆化表然后贪心地在每一步选择排序后第一个能导致可行解的数字保证字典序最小。复杂度- 时间O(n × 2^n × k)其中 n ≤ 13k ≤ 100- 空间O(2^n × k)
