# 第五章 作业3
# 找出所有由1~9组成的9位数，每个数字只能出现一次，且这个9位数由高位到低位前i位能被i整除
#
# 1. 使用深度优先搜索（DFS）来查找满足条件的 9 位数。
#
# 2. 定义一个 `dfs` 函数，两个参数：
#    - `k`：当前已选择的数字个数，初始值为 0。
#    - `num`：当前已选择的数字组成的整数，初始值为 0。
#
# 3. 在 `dfs` 函数中，遍历数字 1 到 9。对于每个数字，检查是否已经使用过（通过 `used` 数组判断）。如果没有使用过，我们尝试将该数字添加到当前的数字组合中。
#
# 4. 检查当前数字组合是否满足条件：前 i 位能被 i 整除。如果满足条件，我们继续递归调用 `dfs`，更新 `k` 和 `num`。
#
# 5. 当 `k` 等于 9 时，找到了一个满足条件的 9 位数。


def find(k: int, num: int, used: list[bool], resultSet: list[int]):
    if k != 0 and num % k != 0:
        return

    if k == 9:
        resultSet.append(num)
        return

    # digit: 1 ~ 9
    for digit in range(1, 10):
        if not used[digit]:
            used[digit] = True
            find(k + 1, num * 10 + digit, used, resultSet)
            # 当前数字撤销使用标记，以便下一个数字的搜索时可用
            used[digit] = False


resultSet = []
find(0, 0, [False] * 10, resultSet)
print(resultSet)