Brute force là gì, và khi nào nó chấp nhận được?

Question

Accepted Answer

**Brute force** (vét cạn) nghĩa là thử mọi ứng viên khả dĩ cho đến khi tìm được đáp án. Nó đơn giản và đảm bảo đúng, nhưng thường chậm — thường là hàm mũ hoặc O(n²).

## Ý tưởng

Liệt kê triệt để toàn bộ không gian lời giải mà không có lối tắt khôn ngoan nào.

## Ví dụ: tìm một cặp có tổng bằng giá trị mục tiêu (vét cạn)

```python
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # kiểm tra mọi cặp
            if nums[i] + nums[j] == target:
                return (i, j)
    return None
# O(n^2) thời gian, O(1) bộ nhớ
```

Một hash map biến cái này thành O(n), nhưng phiên bản vét cạn là điểm khởi đầu hiển nhiên.

## Khi nào chấp nhận được

- **Đầu vào nhỏ** khi hệ số hằng và n đều rất bé.
- Làm **chuẩn cơ sở về tính đúng đắn** để đối chiếu xác thực một thuật toán nhanh hơn.
- Khi bài toán hiếm khi chạy và sự rõ ràng quan trọng hơn tốc độ.
- Trong phỏng vấn, hãy nêu nó trước, rồi mới tối ưu.

## Những cạm bẫy

Vét cạn trên đầu vào lớn gây timeout. Luôn ước lượng kích thước không gian lời giải trước khi cam kết.

## Tại sao điều này quan trọng

Brute force là lời giải đầu tiên trung thực: nó chứng minh bài toán giải được và làm rõ chính xác "đúng" nghĩa là gì.

Nó cho bạn một bản cài đặt tham chiếu để kiểm thử các tối ưu hóa.

Biết khi nào O(n²) hoặc tệ hơn là *đủ tốt* là một kỹ năng kỹ thuật thực thụ — không phải bài toán nào cũng xứng đáng có một thuật toán khôn ngoan.