Mỗi lần đi tiếp có một lần khôi phục
```python
def genBinary_growing(A, k, n):
global count
if k == n:
print(A)
count += 1
else:
for value in range(2):
A.append(value)
genBinary_growing(A, k + 1, n)
A.pop()
```
Bắt đầu với count=0 và genBinary_growing([],0,n). Ở đầu lời gọi, len(A)==k. append thêm lựa chọn nên dãy dài k+1; đệ quy tìm các cách hoàn thành phần còn lại. Khi lời gọi ấy kết thúc, pop bỏ phần tử vừa thêm, khôi phục tiền tố cũ để thử giá trị kế tiếp.
Cơ sở k==n in dãy đủ độ dài rồi tăng count. Sau khi duyệt xong toàn bộ cây, danh sách ban đầu trở lại rỗng.
Theo dõi một lần trở về
Với n=2, đi từ[]đến[0], rồi[0,0]và ghi nghiệm. Sau khi lời gọi ở k=2 kết thúc, pop bỏ0 cuối để A trở lại[0]. Vòng thử tại k=1 chọn 1, tạo[0,1]và ghi nghiệm tiếp.
Kết thúc cả hai lựa chọn ở vị trí thứ hai, trở về mức k=0; pop của mức này bỏ0 đầu để A=[]rồi mới thử 1 ở vị trí đầu. Mỗi mức chỉ xóa phần tử do chính nó thêm.
Đối chiếu hai bản trên cùng n
Chạy co-dinh2 và them-xoa2. Hai bản cần in cùng bốn dãy theo cùng thứ tự và cùng tổng số nghiệm4.
Không chuyển nguyên poptừ bản thêm dần sang bản tạo sẵn: cách giữ trạng thái khác nhau. Nếu quên pop ở bản thêm dần, A vẫn giữ dữ liệu nhánh trước và không còn len(A)==k; kết quả có thể dài sai và mang thêm phần tử cũ.
Bài luyện
Sau khi ghi[0,0], pop ở mức chọn vị trí thứ hai cần đưa A về đâu?
Chỉ bỏ lựa chọn 0 vừa thêm ở cuối.
Đã bỏ cả lựa chọn của mức trước.
Chưa khôi phục trạng thái.
Không phải thao tác đổi phần tử đầu.
Lời giải
Mức đang xét nhận tiền tố[0], append 0 rồi gọi tiếp. Khi quay về, pop xóa phần tử cuối đó và khôi phục[0]trước khi thử 1.
Bài luyện
Nếu pop trước khi gọi đệ quy thì điều gì sai?
Mã yêu cầu append→đệ quy→pop.
Phải đi tiếp với trạng thái đã mở rộng rồi mới khôi phục.
Dãy đã bị thu ngắn trước khi gọi nhỏ.
k+1 không còn khớp độ dài đã chọn.
Lời giải
append đưa giá trị mới vào tiền tố cho lời gọi k+1. Nếu pop ngay trước lời gọi, tiền tố ấy đã mất và bất biến len(A)==k bị phá ở mức tiếp theo.
Bài luyện
Đầu lời gọi đúng ở bản thêm dần có quan hệ nào?
Các mức đã đi tiếp có tiền tố không rỗng.
k tăng khi gọi đệ quy đi tiếp.
Đã chọn k phần tử vào tiền tố A.
Dãy chỉ dài n ở lá, không dài n+1.
Lời giải
Ban đầu dãy rỗng và k=0. Mỗi append đi cùng lời gọi k+1, mỗi popkhôi phục trước lần thử khác, nên quan hệ len(A)==k được giữ.
Bài luyện
Vì sao mỗi mức chỉ pop phần tử chính nó thêm?
Xóa thêm sẽ phá tiền tố của lời gọi trước.
pop chỉ xóa phần tử cuối, không đánh giá lời giải.
Khôi phục trạng thái là phần cần thiết của bản này.
Lựa chọn thuộc mức trước sẽ do mức ấy quản lí.
Lời giải
Mỗi lời gọi chịu trách nhiệm về lựa chọn nó thêm. Sau khi xóa đúng phần tử ấy, trạng thái trả về giống lúc nhận từ mức trước, giúp mức trước tiếp tục đúng.
Đang học