Hướng dẫn giải của Cộng Không Nhớ

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

$N \leq 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.
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)$

Bình luận

Không có bình luận tại thời điểm này.