Cộng Không Nhớ

Lời giải: Cộng Không Nhớ

Hướng tiếp cận

Duyệt tất cả tập con, kiểm tra điều kiện "không nhớ" khi cộng.

Nhận xét quan trọng

1. $N\le 20$ nên có thể duyệt $2^{20}\approx {10}^6$ tập con, hoặc dùng đệ quy có cắt tỉa.
2. Hai số cộng không nhớ khi tổng các chữ số ở mỗi hàng $<10$.

Thuật toán

Đệ quy quay lui: với mỗi số, thử thêm vào nhóm (nếu không tạo nhớ) hoặc bỏ qua. Cắt tỉa khi số phần tử còn lại không đủ để vượt kết quả tốt nhất.

Độ phức tạp

• Thời gian: $O(2^N)$ trường hợp xấu nhất, thực tế nhanh hơn nhờ cắt tỉa
• Bộ nhớ: $O(N)$