O padrão em 30 segundos
Busca exaustiva com arrependimento: tenta uma escolha, desce na recursão, desfaz e tenta a próxima. Gera subsets, permutações, combinações; resolve N-Queens e word search. O esqueleto é sempre o mesmo: escolher → recursar → desfazer.
Como reconhecer na hora
- "Gere TODAS as combinações/permutações/subsets"
- Tabuleiro/grade com restrições (N-Queens, Sudoku, word search)
- Decisões em sequência onde cada uma restringe as próximas
Esquecer de DESFAZER a escolha depois da recursão (o pop do path), ou copiar o array de estado a cada nível sem necessidade, explodindo memória. E sempre declare: o custo é exponencial no pior caso; pruning corta ramos (às vezes muitos), mas não torna o problema polinomial.
Complexidade típica: Exponencial por natureza (2^n subsets, n! permutações). Dizer isso com calma é parte da resposta certa.
Os 9 problemas da categoria
| Problema | Dificuldade | Nível no VagaGringa |
|---|---|---|
| Subsets cai muito | medium | nível 2 |
| Combination Sum cai muito | medium | nível 2 · core |
| Permutations cai muito | medium | nível 2 |
| Subsets II | medium | nível 3 |
| Combination Sum II | medium | nível 3 |
| Word Search cai muito | medium | nível 2 · core |
| Palindrome Partitioning | medium | nível 3 |
| Letter Combinations of a Phone Number | medium | nível 3 |
| N-Queens | hard | nível 4 |
No VagaGringa, esses 9 problemas entram numa trilha de 4 níveis com marcação do que mais cai em entrevista, e você registra tentativa, revisão e domínio de cada um.
Abrir a trilha NeetCode no app