Qu'est-ce que la force brute et quand est-ce acceptable ?

Question

Accepted Answer

**Force brute** signifie essayer chaque candidat possible jusqu'à trouver la réponse. C'est simple et garanti correct, mais souvent lent — généralement exponentiel ou O(n²).

## L'idée

Énumérer exhaustivement l'espace des solutions sans raccourcis malins.

## Exemple : trouver une paire qui additionne à une cible (force brute)

```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
```

Une hash map transforme cela en O(n), mais la version force brute est le point de départ évident.

## Quand c'est acceptable

- **Petites entrées** où le facteur constant et n sont minuscules.
- En tant que **ligne de base de correction** pour valider un algorithme plus rapide.
- Quand le problème s'exécute rarement et que la clarté prime sur la vitesse.
- Pendant les entretiens, énoncez-le d'abord, puis optimisez.

## Pièges

La force brute sur de grandes entrées cause des timeouts. Estimez toujours la taille de l'espace des solutions avant de vous engager.

## Pourquoi c'est important

La force brute est la première solution honnête : elle prouve que le problème est résoluble et clarifie exactement ce que « correct » signifie.

Elle vous donne une implémentation de référence pour tester les optimisations.

Savoir quand O(n²) ou pire est *suffisant* est une vraie compétence d'ingénieur — tous les problèmes ne méritent pas un algorithme astucieux.