2025-10-19：判断连接可整除性用go语言，给出一个仅含正整数的

摘要：把 nums 中元素按某种顺序排列，然后把这些整数按顺序拼接成一个十进制字符串并看作一个大整数（例如 [12,3,45] 拼成 12345）。

2025-10-19：判断连接可整除性。用go语言，给出一个仅含正整数的数组 nums 和一个正整数 k。

把 nums 中元素按某种顺序排列，然后把这些整数按顺序拼接成一个十进制字符串并看作一个大整数（例如 [12,3,45] 拼成 12345）。

如果这个大整数能被 k 整除，就称该排列是合法的。

要求在所有合法排列里选出按字典序（从左到右逐项比较）最小的那个，并以整数列表的形式返回；若没有任何合法排列，则返回空列表。

输入: nums = [3,12,45], k = 5。

输出: [3,12,45]。
解释:

排列连接后的值是否能被 5 整除[3, 12, 45]31245是[3, 45, 12]34512否[12, 3, 45]12345是[12, 45, 3]12453否[45, 3, 12]45312否[45, 12, 3]45123否

可以形成可整除连接且字典序最小的排列是 [3,12,45]。

题目来自力扣3533。

首先对 nums 进行升序排序。
这是为了在 DFS 枚举时，按数字从小到大的顺序尝试，这样一旦找到解，就是字典序最小的解（因为 DFS 找到的第一个解是按数字从小到大的顺序构造的）。

对于每个数字 nums[i]，计算它作为字符串时的长度，然后计算 10^长度，存入 pow10[i]。
例如 nums[i] = 45，长度是 2，pow10[i] = 100。
这个数组的作用是：当我们把某个数字 nums[j] 拼接到当前数字 x 后面时，相当于 x * pow10[j] + nums[j]。

s 是一个位掩码（bitmask），表示哪些数字已经被使用（1 表示已用，0 表示未用）。x 是当前已拼接的数字对 k 取模的结果（避免大数运算）。

• 初始状态：s = (1

• 目标状态：s = 0（所有数字都用完）且 x == 0（模 k 为 0，即整除）。

1. 如果 s == 0，检查 x == 0，是则返回 true 表示找到解。

2. 如果 vis[s][x] 为 true，说明之前从这个状态出发没找到解，直接返回 false（避免重复搜索）。

3. 标记 vis[s][x] = true。

4. 枚举 s 中为 1 的位（即未使用的数字），按 nums 排序后的顺序（因为循环是从低位到高位，但 nums 已排序，所以先试小的数字）。

• 移除该位 s' = s ^ (1

• 新余数 x' = (x * pow10[i] + nums[i]) % k

• 递归 dfs(s', x')

• 如果返回 true，说明找到解，把 nums[i] 加入答案列表，并返回 true。

5. 如果所有枚举都不行，返回 false。

• 因为 DFS 找到解时，是从最后一个数字开始往前加入 ans 的（递归回溯时添加），所以最后需要反转 ans 才能得到正确的顺序。

• 如果 DFS 返回 false，返回 nil。

1. 排序后 nums = [3,12,45]

2. pow10 = [10, 100, 100]（因为 3 长度 1 → 10^1=10，12 长度 2 → 100，45 长度 2 → 100）

3. DFS 从 s=111b, x=0 开始，尝试：

• 选 3：s=110b, x = (0*10+3)%5 = 3

• 选 12：s=100b, x = (3*100+12)%5 = 312%5 = 2

• 选 45：s=000b, x = (2*100+45)%5 = 245%5 = 0 ✅ 找到解

• 回溯添加顺序：45 → 12 → 3

• 反转后得到 [3,12,45]

• 状态数：(1

• 每个状态最多尝试 n 种转移。

• 所以时间复杂度为 O(2^n * n * k)。

• 这里 n ≤ 13，k ≤ 100，所以可行。

• 记忆化数组 vis 大小：2^n * k，即 O(2^n * k)。

• pow10 数组：O(n)。

• DFS 递归栈深度：O(n)。

• 总额外空间复杂度：O(2^n * k)。

总结
该算法通过状态压缩 DFS + 记忆化搜索，按排序顺序枚举排列，保证找到的第一个解就是字典序最小的合法排列。
时间复杂度 O(2^n * n * k)，空间复杂度 O(2^n * k)。

package mainimport ( "fmt" "math" "math/bits" "slices" "strconv")func concatenatedDivisibility(nums int, k int) int { slices.Sort(nums) n := len(nums) pow10 := make(int, n) for i, x := range nums { pow10[i] = int(math.Pow10(len(strconv.Itoa(x)))) } ans := make(int, 0, n) vis := make(bool, 10; t &= t - 1 { i := bits.TrailingZeros(t) if dfs(s^1

# -*-coding:utf-8-*-import mathfrom typing import Listdef concatenatedDivisibility(nums: List[int], k: int) -> List[int]: nums.sort n = len(nums) # 预计算每个数字的10的幂次 pow10 = [10 ** len(str(x)) for x in nums] ans = # 记忆化数组：vis[state][remainder] vis = [[False] * k for _ in range(1 bool: if s == 0: return x == 0 if vis[s][x]: return False vis[s][x] = True # 枚举在状态s中的每个数字 for i in range(n): if s & (1