Sinh dãy ADN bằng quay lui

Bài toán dùng các kí hiệu nucleotit A,T,G,X để biểu diễn một đoạn mạch đơn ADN dài n. Trong mô hình sinh dãy của bài, mỗi vị trí được chọn một trong bốn kí tự; cùng kí tự có thể xuất hiện ở nhiều vị trí, như AA hoặc TT. Giống bản nhị phân tạo sẵn, khởi tạo A có n chỗ rồi gán lần lượt từng vị trí. Tới k==n thì đã có một dãy đủ độ dài. Số kết quả là $4^n$, tăng nhanh nên thực hành với n nhỏ.

```python def genDNASection(A, k, n, as_string=False): global count if k == n: print(''.join(A) if as_string else A) count += 1 else: for value in 'ATGX': A[k] = value genDNASection(A, k + 1, n, as_string) ``` Đặt count=0 trước khi gọi genDNASection(['']*n,0,n). Mặc định hàm in danh sách các kí tự. Nếu tham số as_string=True thì tại lá dùng ''.join(A) để in xâu liền nhau; hai kiểu xuất có cùng các lựa chọn và số nghiệm. Với n=1, nhận A,T,G,X. Với n=2, có 16 kết quả, bắt đầu AA,AT,AG,AX rồi tới các nhánh bắt đầu T,G,X; kết thúc XX. Dãy tạo sẵn chỉ gán đè nên không cần pop.