Python - Backtracking

Backtracking là một dạng đệ quy. Nhưng nó liên quan đến việc chọn lựa chọn duy nhất trong số bất kỳ khả năng nào. Chúng tôi bắt đầu bằng cách chọn một tùy chọn và quay lại từ đó, nếu chúng tôi đạt đến trạng thái mà chúng tôi kết luận rằng tùy chọn cụ thể này không đưa ra giải pháp cần thiết. Chúng tôi lặp lại các bước này bằng cách xem qua từng tùy chọn có sẵn cho đến khi chúng tôi nhận được giải pháp mong muốn.

Dưới đây là một ví dụ về việc tìm tất cả các thứ tự sắp xếp có thể có của một bộ chữ cái nhất định. Khi chúng tôi chọn một cặp, chúng tôi áp dụng theo dõi ngược để xác minh xem cặp chính xác đó đã được tạo hay chưa. Nếu chưa được tạo, cặp này sẽ được thêm vào danh sách câu trả lời, nếu không thì sẽ bị bỏ qua.

def permute(list, s):
    if list == 1:
        return s
    else:
        return [ y + x
                 for y in permute(1, s)
                 for x in permute(list - 1, s)
                 ]

print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']