Concatenated divisibility

impl Solution {
  pub fn concatenated_divisibility(mut nums: Vec<i32>, k: i32) -> Vec<i32> {
    let n = nums.len();
    let k = k as usize;
    nums.sort_unstable(); // sort for lex-smallest

    // Precompute: power[i] = 10^(len(nums[i])) mod k
    let pow_mod: Vec<usize> = nums
      .iter()
      .map(|&x| {
        let digits = x.to_string().len();
        let mut p = 1usize;
        for _ in 0..digits {
          p = p * 10 % k;
        }
        p
      })
      .collect();

    // dp[mask][rem] = true if achievable; also track choice for reconstruction
    // But for lex-smallest we try elements in sorted order and take first feasible
    // dp[mask] = remainder after processing exactly the elements in mask (lex-first order)
    // We only store ONE reachable remainder per mask (greedy approach won't work directly for lex)
    // Instead: dp[mask][rem] = bool; reconstruct greedily

    let states = 1usize << n;
    let mut dp = vec![vec![false; k]; states];
    dp[0][0] = true;

    for mask in 0..states {
      for rem in 0..k {
        if !dp[mask][rem] { continue; }
        for i in 0..n {
          if mask & (1 << i) != 0 { continue; }
          let next_mask = mask | (1 << i);
          // appending nums[i]: new_rem = rem * 10^len(nums[i]) + nums[i] mod k
          let new_rem = (rem * pow_mod[i] + nums[i] as usize % k) % k;
          dp[next_mask][new_rem] = true;
        }
      }
    }

    let full = states - 1;
    if !dp[full][0] {
      return vec![];
    }

    // Reconstruct: greedily pick the smallest-indexed (already sorted) valid next element
    let mut result = Vec::with_capacity(n);
    let mask = 0usize;
    let rem = 0usize;

    for _ in 0..n {
      for i in 0..n {
        if mask & (1 << i) != 0 { continue; }
        let new_rem = (rem * pow_mod[i] + nums[i] as usize % k) % k;
        let next_mask = mask | (1 << i);
        // Check if choosing i here can lead to full mask with rem=0
        let remaining_full = full ^ mask; // all remaining bits
        let next_remaining = remaining_full ^ (1 << i);
        // We need dp[next_mask..full] to be reachable with rem 0
        // More precisely: we need there to exist some completion from next_mask with rem new_rem ending at 0
        // dp[full][0] reachable from (next_mask, new_rem)?
        // We stored dp forward, so we need reverse check
        // Alternative: check if dp[full][0] is reachable via this prefix
        // We need a "suffix" dp: can we complete from (next_mask, new_rem) to (full, 0)?
        let _ = next_remaining;
        // Use precomputed dp: dp[next_mask][new_rem] says we CAN reach this state
        // But we also need to ensure (full, 0) is reachable FROM (next_mask, new_rem)
        // So we need a reverse DP or suffix DP.
        // Let's compute suffix: suffix[mask][rem] = true if from mask with remainder rem we can reach (full, 0)
        // We'll compute it lazily here or precompute below.
        // Actually let's just precompute suffix dp above the loop.
        let _ = new_rem;
        let _ = next_mask;
        break; // placeholder
      }
      break; // placeholder
    }
    result.clear();

    // Recompute with suffix DP for reconstruction
    // suffix[mask][rem] = can complete from (mask used, current_rem) to get total rem 0?
    let mut suf = vec![vec![false; k]; states];
    suf[full][0] = true;
    // traverse masks from full down to 0
    for mask in (0..states).rev() {
      for rem in 0..k {
        if !suf[mask][rem] { continue; }
        // which element to "un-pick"? we process forward, so let's build suf differently
        // Actually easier: build suffix by considering which element was last added
        // suf[mask][rem] = true means: if we've used elements in mask and current rem = rem, we can finish
        // So from (mask without i, prev_rem) -> (mask, rem) means prev_rem * pow[i] + nums[i] ≡ rem (mod k)
        // Let's just rebuild by iterating forward contributions
        let _ = rem;
      }
    }
    drop(suf);

    // Simpler: Use forward dp already computed + reachability check
    // For reconstruction: at each step pick smallest i s.t. dp[next_mask][new_rem] && can_complete
    // can_complete(next_mask, new_rem) = exists a path from (next_mask, new_rem) to (full, 0)
    // Compute can_complete via reverse BFS / reverse DP:
    let mut can = vec![vec![false; k]; states];
    // Base: can[full][0] = true
    can[full][0] = true;
    // Iterate masks from high to low popcount
    // For mask with popcount p, can[mask][rem] = true if exists i not in mask s.t.
    //   new_rem = (rem * pow[i] + nums[i]) % k and can[mask|(1<<i)][new_rem]
    // We need descending order of popcount.
    let mut masks_by_pop: Vec<usize> = (0..states).collect();
    masks_by_pop.sort_unstable_by_key(|m| std::cmp::Reverse(m.count_ones()));
    for &mask in &masks_by_pop {
      for rem in 0..k {
        if mask == full {
          // already set
          continue;
        }
        for i in 0..n {
          if mask & (1 << i) != 0 { continue; }
          let new_rem = (rem * pow_mod[i] + nums[i] as usize % k) % k;
          let next_mask = mask | (1 << i);
          if can[next_mask][new_rem] {
            can[mask][rem] = true;
            break;
          }
        }
      }
    }

    let mut mask = 0usize;
    let mut rem = 0usize;
    for _ in 0..n {
      for i in 0..n {
        if mask & (1 << i) != 0 { continue; }
        let new_rem = (rem * pow_mod[i] + nums[i] as usize % k) % k;
        let next_mask = mask | (1 << i);
        if can[next_mask][new_rem] {
          result.push(nums[i]);
          mask = next_mask;
          rem = new_rem;
          break;
        }
      }
    }

    result
  }
}