下标从 0 开始的整数数组 nums 特殊排列的总数目 - 回溯算法详解 - 常规

下标从 0 开始的整数数组 nums 特殊排列的总数目 - 回溯算法详解

给定一个下标从 0 开始的整数数组 nums，它包含 n 个互不相同的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：

对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。

请你返回特别排列的总数目，n 最大为 14。

思路：回溯法

对于每一个位置 i，我们可以枚举当前未使用的数字中可以放在 i 位置的数，然后判断是否满足条件。如果满足条件，则递归到下一个位置，否则继续枚举下一个数。如果枚举完所有数都不满足条件，则回溯到上一个位置，继续枚举下一个数。

具体来说，我们可以用一个布尔数组 used 来记录哪些数字已经被使用过了，用一个数组 perm 来记录当前排列的状态，用一个变量 count 来记录合法排列的总数。

代码：

def countSpecialPermutations(nums):
    n = len(nums)
    used = [False] * n
    perm = [0] * n
    count = 0

    def backtrack(i):
        nonlocal count
        if i == n:
            count += 1
            return

        for j in range(n):
            if not used[j]:
                if i == 0 or (nums[perm[i-1]] % nums[j] == 0 or nums[j] % nums[perm[i-1]] == 0):
                    perm[i] = j
                    used[j] = True
                    backtrack(i + 1)
                    used[j] = False

    backtrack(0)
    return count

解释：

函数 countSpecialPermutations(nums):
- 定义一个布尔数组 used 来记录每个数字是否被使用过，初始化为 False。
- 定义一个数组 perm 来存储当前排列，初始化为 0。
- 定义一个变量 count 来记录合法排列的总数，初始化为 0。
- 调用 backtrack 函数开始回溯，从位置 0 开始。
函数 backtrack(i):
- 当 i 等于 n 时，说明已经找到一个合法排列，count 加 1 并返回。
- 遍历所有数字 (j)，如果数字 j 没有被使用过，且满足条件 (i == 0 或 nums[perm[i-1]] % nums[j] == 0 或 nums[j] % nums[perm[i-1]] == 0)，则将 j 放入 perm[i]，将 used[j] 设置为 True，并递归调用 backtrack(i + 1) 继续寻找下一个位置的数字。
- 回溯时，将 used[j] 设置为 False，表示 j 再次可用。

示例：

nums = [1, 2, 3, 4]
count = countSpecialPermutations(nums)
print(count)  # 输出 8

注意：

该代码的时间复杂度为 O(n!)，因为在最坏情况下需要枚举所有排列。
对于 n 最大为 14 的情况，该算法仍然能够在合理时间内运行。
该代码使用回溯算法，通过递归和状态记录来枚举所有可能的排列，并筛选出满足条件的排列。