Kiểm tra số có chia hết cho số tạo từ chữ số {A, B} không (Python)

Bài toán: Cho n, a, b. Kiểm tra có tồn tại số tạo từ các chữ số a và b (ví dụ: 23, 32, 223, 332...) mà chia hết n không.

Đệ quy quay lui (Backtracking)

Sinh tất cả số có thể tạo từ a, b (thêm chữ số bên phải: temp*10 + a hoặc temp*10 + b) cho đến khi > n.

Triển khai Python

def util(temp, a, b, n):
    if temp > n:
        return False
    if n % temp == 0:
        return True
    return util(temp * 10 + a, a, b, n) or util(temp * 10 + b, a, b, n)

def solve(n, a, b):
    return util(a, a, b, n) or util(b, a, b, n)

# Test
print(solve(115, 3, 2))  # True: 115 % 23 == 0 (23 từ {2,3})
print(solve(100, 2, 5))  # True: 100 % 25 == 0
print(solve(17, 2, 3))   # False

Kết quả

True

Giải thích

• Hàm util đệ quy sinh số: bắt đầu từ a hoặc b, mỗi bước thêm a hoặc b bên phải.
• Dừng khi temp > n (vì số lớn hơn n không thể chia hết n trừ khi n=0).
• Nếu n % temp == 0 → tìm thấy ước số thỏa mãn.
• Độ phức tạp số lượng số sinh ra: O(2^d) với d = số chữ số của n.