Ce este brute force și când este acceptabil?

Question

Accepted Answer

**Brute force** înseamnă a încerca fiecare candidat posibil până găsești răspunsul. Este simplu și garantat corect, dar adesea lent — frecvent exponențial sau O(n²).

## Ideea

Enumerarea exhaustivă a spațiului soluției fără scurtături inteligente.

## Exemplu: găsirea unei perechi care însumează la o țintă (brute force)

```python
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # check every pair
            if nums[i] + nums[j] == target:
                return (i, j)
    return None
# O(n^2) time, O(1) space
```

O hartă hash transformă aceasta în O(n), dar versiunea brute-force este punctul de plecare evident.

## Când este acceptabil

- **Intrări mici** unde factorul constant și n sunt minusculi.
- Ca **linie de bază pentru corectitudine** pentru a valida un algoritm mai rapid.
- Când problema se execută rar și claritatea bate viteza.
- În timpul interviului, prezintă-o mai întâi, apoi optimizează.

## Capcane

Brute force pe intrări mari provoacă timeout-uri. Estimează întotdeauna dimensiunea spațiului soluției înainte de a te angaja.

## De ce este important

Brute force este prima soluție onestă: dovedește că problema este rezolvabilă și clarifică exact ce înseamnă "corect".

Îți oferă o implementare de referință pentru a testa optimizările.

A ști când O(n²) sau mai rău este *suficient de bun* este o abilitate reală de inginerie — nu fiecare problemă merită un algoritm inteligent.