Blog

Backtracking em C#: subconjuntos, permutações e N rainhas

Escrito por

Backtracking é o padrão com o núcleo menor e o alcance maior. Todo problema aqui é as mesmas três linhas com uma regra de ramificação diferente.

choose      — add to the current state
explore     — recurse
un-choose   — take it back out

Os caminhos da raiz à folha da parte 13 já usaram isso. É para isto que ele existe.

Todo programa abaixo está completo, rodou no .NET 10, e a saída é colada da execução.

Padrão 71 — Subconjuntos

Todo subconjunto de um conjunto. Para cada elemento há duas escolhas, então a busca é uma árvore binária de n níveis de profundidade.

[] pega 1 pula 1 1 [] 1,2 1 2 [] Todo nó da árvore é um subconjunto. São n níveis e dois ramos em cada um, então são 2ⁿ ao todo — e a recursão registra um em cada nó, não só nas folhas.

Subconjuntos, permutações, combinações e N rainhas são todos esta mesma árvore com regras de ramificação diferentes. A recursão desce por um caminho, registra o que tem, e então devolve tudo ao lugar antes de tentar o próximo ramo.

int[] a = [1, 2, 3];
List<List<int>> all = [];
List<int> current = [];

// The template every problem in this part is an instance of:
//   record the state, try each choice, UNDO the choice.
void Explore(int start, int depth)
{
    all.Add([.. current]);       // a copy — `current` keeps changing under us
    Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", current)}]");

    for (int i = start; i < a.Length; i++)
    {
        current.Add(a[i]);            // choose
        Explore(i + 1, depth + 1);    // explore, from AFTER i so nothing repeats
        current.RemoveAt(current.Count - 1);   // un-choose
    }
}

Explore(0, 0);
Console.WriteLine($"\n{all.Count} subsets, expected 2^{a.Length} = {1 << a.Length}");

// The same thing without recursion: each bit of a counter says include or not.
Console.WriteLine("\nby bitmask, no recursion at all:");
for (int mask = 0; mask < (1 << a.Length); mask++)
{
    var pick = Enumerable.Range(0, a.Length).Where(i => (mask & (1 << i)) != 0).Select(i => a[i]);
    Console.WriteLine($"  {Convert.ToString(mask, 2).PadLeft(a.Length, '0')} -> [{string.Join(",", pick)}]");
}

Ele imprime:

[]
  [1]
    [1,2]
      [1,2,3]
    [1,3]
  [2]
    [2,3]
  [3]

8 subsets, expected 2^3 = 8

by bitmask, no recursion at all:
  000 -> []
  001 -> [1]
  010 -> [2]
  011 -> [1,2]
  100 -> [3]
  101 -> [1,3]
  110 -> [2,3]
  111 -> [1,2,3]

Dois detalhes sustentam tudo.

all.Add([.. current]) copia. current é uma lista só, que fica sendo mutada, então guardar uma referência a ela faz cada entrada de all apontar para o mesmo objeto — e no fim esse objeto está vazio. O spread da collection expression é a cópia.

O registro acontece em cada nó, não nas folhas. Um subconjunto não é “um caminho completo até o fundo”, é qualquer nó da árvore, e é por isso que all.Add fica antes do laço, e não dentro de um caso base.

A versão com bitmask no fim é a mesma enumeração sem recursão, e liga ao padrão 45 da parte 9. Para subconjuntos, ela costuma ser a melhor resposta — sem pilha, sem desfazer, e os bits são as decisões de incluir ou não.

Custo: O(2ⁿ) subconjuntos, O(n · 2ⁿ) para escrever todos.

Use quando o problema pede todos os subconjuntos, o conjunto das partes, ou todas as combinações de qualquer tamanho.

Padrão 72 — Permutações

Toda ordem possível. São n! delas, então isso só é viável para n pequeno.

A implementação óbvia mantém um array used[] e monta uma lista nova por ramo. A versão com troca não precisa de nenhum dos dois.

int[] a = [1, 2, 3];
List<string> all = [];

// Swap the chosen element into position, recurse on the rest, swap it back.
// No "used" array, no allocation per branch.
void Permute(int k, int depth)
{
    if (k == a.Length)
    {
        all.Add(string.Join(",", a));
        Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", a)}]  <- complete");
        return;
    }

    for (int i = k; i < a.Length; i++)
    {
        (a[k], a[i]) = (a[i], a[k]);            // choose: a[i] goes to position k
        Console.WriteLine($"{new string(' ', depth * 2)}position {k} := {a[k]}   array now [{string.Join(",", a)}]");
        Permute(k + 1, depth + 1);
        (a[k], a[i]) = (a[i], a[k]);            // un-choose: put it back
    }
}

Permute(0, 0);
Console.WriteLine($"\n{all.Count} permutations, expected {a.Length}! = {Enumerable.Range(1, a.Length).Aggregate(1, (x, y) => x * y)}");
Console.WriteLine($"array restored to its original order: [{string.Join(",", a)}]");

Ele imprime:

position 0 := 1   array now [1,2,3]
  position 1 := 2   array now [1,2,3]
    position 2 := 3   array now [1,2,3]
      [1,2,3]  <- complete
  position 1 := 3   array now [1,3,2]
    position 2 := 2   array now [1,3,2]
      [1,3,2]  <- complete
position 0 := 2   array now [2,1,3]
  position 1 := 1   array now [2,1,3]
    position 2 := 3   array now [2,1,3]
      [2,1,3]  <- complete
  position 1 := 3   array now [2,3,1]
    position 2 := 1   array now [2,3,1]
      [2,3,1]  <- complete
position 0 := 3   array now [3,2,1]
  position 1 := 2   array now [3,2,1]
    position 2 := 1   array now [3,2,1]
      [3,2,1]  <- complete
  position 1 := 1   array now [3,1,2]
    position 2 := 2   array now [3,1,2]
      [3,1,2]  <- complete

6 permutations, expected 3! = 6
array restored to its original order: [1,2,3]

Troque o elemento escolhido para a posição k, recorra em k+1, depois troque de volta. A posição k está decidida; tudo de k em diante ainda está disponível, em alguma ordem.

A última linha dessa saída é a verificação que vale manter: o array volta à ordem original quando tudo termina. Se não voltar, falta um passo de desfazer em algum lugar — e isso é bem mais fácil de notar do que uma permutação errada enterrada numa lista de centenas.

A versão com troca não produz as permutações em ordem lexicográfica, e a saída mostra isso. Se o problema quer a saída ordenada, ordene depois ou use a versão com used[].

Custo: O(n!) resultados, O(n) de espaço extra.

Use quando o problema é sobre ordens, arranjos ou geração de anagramas.

Padrão 73 — Poda

Backtracking sozinho é busca exaustiva. A poda é o que o torna usável, e é onde estão os ganhos reais.

int[] candidates = [2, 3, 6, 7];
int target = 7;

Array.Sort(candidates);          // sorting is what makes the pruning possible
List<List<int>> found = [];
List<int> current = [];
int calls = 0, pruned = 0;

void Search(int start, int remaining, int depth)
{
    calls++;
    if (remaining == 0)
    {
        found.Add([.. current]);
        Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", current)}]  <- sums to {target}");
        return;
    }

    for (int i = start; i < candidates.Length; i++)
    {
        if (candidates[i] > remaining)
        {
            // Sorted, so every candidate after this one is bigger too.
            pruned += candidates.Length - i;
            Console.WriteLine($"{new string(' ', depth * 2)}{candidates[i]} > {remaining}, and the rest are larger -> prune {candidates.Length - i} branches");
            break;
        }
        current.Add(candidates[i]);
        Search(i, remaining - candidates[i], depth + 1);   // i, not i+1: reuse allowed
        current.RemoveAt(current.Count - 1);
    }
}

Search(0, target, 0);
Console.WriteLine($"\nsolutions: {string.Join("  ", found.Select(f => "[" + string.Join(",", f) + "]"))}");
Console.WriteLine($"recursive calls: {calls}, branches pruned: {pruned}");
Console.WriteLine($"\nSearch(i, ...) rather than Search(i + 1, ...) lets a candidate repeat.");
Console.WriteLine($"Starting at i rather than 0 is what stops [2,2,3] and [2,3,2] both appearing.");

Ele imprime:

      2 > 1, and the rest are larger -> prune 4 branches
      [2,2,3]  <- sums to 7
    6 > 3, and the rest are larger -> prune 2 branches
    3 > 2, and the rest are larger -> prune 3 branches
  6 > 5, and the rest are larger -> prune 2 branches
    3 > 1, and the rest are larger -> prune 3 branches
  6 > 4, and the rest are larger -> prune 2 branches
  6 > 1, and the rest are larger -> prune 2 branches
  [7]  <- sums to 7

solutions: [2,2,3]  [7]
recursive calls: 10, branches pruned: 18

Search(i, ...) rather than Search(i + 1, ...) lets a candidate repeat.
Starting at i rather than 0 is what stops [2,2,3] and [2,3,2] both appearing.

Ordenar os candidatos primeiro é o que torna a poda possível. Assim que candidates[i] > remaining, todo candidato depois dele também é maior, então o resto do laço pode ser abandonado com break em vez de continue. Dezoito ramos nunca explorados, numa entrada de quatro números.

Dois detalhes de índice, e eles são diferentes um do outro:

  • Search(i, ...) em vez de Search(i + 1, ...) deixa um candidato ser reusado, e é isso que torna [2,2,3] válido aqui.
  • Começar o laço em start e não em 0 é o que impede [2,2,3] e [2,3,2] de serem relatados os dois. Combinações não têm ordem; só sequências não decrescentes são geradas.

Custo: exponencial no pior caso, e muitas vezes bem melhor. A poda é o algoritmo.

Use quando a busca exaustiva é o formato certo mas a árvore inteira é grande demais — soma de combinações, particionamento, problemas com restrições.

Padrão 74 — Duplicatas na entrada

Dado [1, 2, 2], relate cada subconjunto distinto uma vez só.

entrada 1 2 2 i=0i=1i=2 num nível, start=1 i=1: primeiro 2, pega i=2: mesmo valor, mesmo nível → pula mais fundo, start=2 agora i=2 é i == start → permitido, dá [2,2] O teste é i > start, não i > 0. Usar o segundo 2 como escolha POSTERIOR num nível repete um ramo;

Usá-lo como primeira escolha mais fundo dá um subconjunto realmente novo. É por isso que a condição compara com start e não com zero — e por isso [2,2] sobrevive enquanto o [2] duplicado não.

int[] a = [1, 2, 2];
Array.Sort(a);                    // duplicates must be ADJACENT for the skip to work

static List<string> Subsets(int[] a, bool skipDuplicates)
{
    List<string> all = [];
    List<int> current = [];

    void Explore(int start)
    {
        all.Add("[" + string.Join(",", current) + "]");
        for (int i = start; i < a.Length; i++)
        {
            // At this level, a repeated value would rebuild a branch already done.
            // i > start is the key: the FIRST 2 at a level is fine, the second is not.
            if (skipDuplicates && i > start && a[i] == a[i - 1]) continue;
            current.Add(a[i]);
            Explore(i + 1);
            current.RemoveAt(current.Count - 1);
        }
    }
    Explore(0);
    return all;
}

var naive = Subsets(a, false);
var fixed_ = Subsets(a, true);

Console.WriteLine($"input: [{string.Join(",", a)}]\n");
Console.WriteLine($"without the skip: {string.Join(" ", naive)}");
Console.WriteLine($"  {naive.Count} results, {naive.Distinct().Count()} of them distinct");
Console.WriteLine($"  repeated: {string.Join(" ", naive.GroupBy(x => x).Where(g => g.Count() > 1).Select(g => g.Key))}");

Console.WriteLine($"\nwith the skip:    {string.Join(" ", fixed_)}");
Console.WriteLine($"  {fixed_.Count} results, {fixed_.Distinct().Count()} of them distinct");

Console.WriteLine($"\ni > start, not i > 0. Using the second 2 as the FIRST pick at a level");
Console.WriteLine($"is a new branch; using it as a LATER pick repeats one already taken.");
Console.WriteLine($"That is a different bug from part 1's duplicate anchors, and it needs");
Console.WriteLine($"its own condition.");

Ele imprime:

input: [1,2,2]

without the skip: [] [1] [1,2] [1,2,2] [1,2] [2] [2,2] [2]
  8 results, 6 of them distinct
  repeated: [1,2] [2]

with the skip:    [] [1] [1,2] [1,2,2] [2] [2,2]
  6 results, 6 of them distinct

i > start, not i > 0. Using the second 2 as the FIRST pick at a level
is a new branch; using it as a LATER pick repeats one already taken.
That is a different bug from part 1's duplicate anchors, and it needs
its own condition.

Sem o pulo: oito resultados, seis distintos, com [1,2] e [2] aparecendo duas vezes cada.

A correção é if (i > start && a[i] == a[i - 1]) continue; num array ordenado. A condição é tudo, e a comparação é contra start, não contra zero:

  • Num nível, escolher o segundo 2 reconstrói um ramo que o primeiro 2 já construiu. Pule.
  • Mais fundo, onde start já passou do primeiro 2, i == start e o segundo 2 é a primeira escolha daquele nível — um subconjunto realmente novo. Permita. É assim que [2,2] sobrevive.

O 3Sum da parte 1 também tinha um problema de duplicatas, e era um outro — pular âncoras repetidas numa varredura com dois ponteiros. Mesma palavra, bug diferente, correção diferente. Nenhuma das duas condições ajuda com a outra.

Use quando a entrada pode conter repetições e a saída não pode.

Padrão 75 — N rainhas

Coloque n rainhas num tabuleiro n × n de forma que nenhuma ataque outra.

Q Uma rainha por LINHA já está na forma da recursão — Place(row + 1) — então essa regra nunca é testada. Só restam dois testes: mesma coluna col[r] == c mesma diagonal |col[r] − c| == row − r As casas cinzas já estão descartadas.

Codificar uma restrição na forma da busca é melhor que testá-la. Como cada chamada recursiva é dona de uma linha, o tabuleiro é um int[n] de posições de coluna em vez de uma grade, e a regra da linha vale por construção.

int n = 4;
int[] col = new int[n];        // col[r] = which column the queen in row r sits in
List<string[]> solutions = [];
int placed = 0, rejected = 0;

bool Safe(int row, int c)
{
    for (int r = 0; r < row; r++)
    {
        if (col[r] == c) return false;                       // same column
        if (Math.Abs(col[r] - c) == row - r) return false;    // same diagonal
    }
    return true;
}

void Place(int row)
{
    if (row == n)
    {
        solutions.Add([.. Enumerable.Range(0, n).Select(r => new string('.', col[r]) + "Q" + new string('.', n - col[r] - 1))]);
        Console.WriteLine($"  solution: columns {string.Join(",", col)}");
        return;
    }

    for (int c = 0; c < n; c++)
    {
        if (!Safe(row, c)) { rejected++; continue; }
        col[row] = c;                 // choose
        placed++;
        Place(row + 1);               // explore
        // un-choose is implicit: col[row] is overwritten next iteration and
        // never read for rows >= the current one.
    }
}

Console.WriteLine($"{n}-queens:");
Place(0);

Console.WriteLine($"\n{solutions.Count} solutions");
foreach (var s in solutions)
{
    Console.WriteLine();
    foreach (string row in s) Console.WriteLine($"  {row}");
}

Console.WriteLine($"\nplacements tried: {placed}, rejected by Safe: {rejected}");
Console.WriteLine($"brute force would test {Math.Pow(n, n):N0} arrangements");
Console.WriteLine();
Console.WriteLine("One queen per row is built into the shape of the recursion, so that");
Console.WriteLine("constraint never has to be checked. Only columns and diagonals are.");

Ele imprime:

4-queens:
  solution: columns 1,3,0,2
  solution: columns 2,0,3,1

2 solutions

  .Q..
  ...Q
  Q...
  ..Q.

  ..Q.
  Q...
  ...Q
  .Q..

placements tried: 16, rejected by Safe: 44
brute force would test 256 arrangements

One queen per row is built into the shape of the recursion, so that
constraint never has to be checked. Only columns and diagonals are.

A decisão de projeto que vale levar é que uma rainha por linha já está na forma da recursão. Place(row + 1) significa que cada chamada é dona de exatamente uma linha, então “duas rainhas nunca dividem uma linha” é verdade por construção e nunca é testado.

Isso também encolhe o estado. O tabuleiro não é uma grade n × n e sim um int[n] — col[r] é onde a rainha da linha r está. Só restam dois testes: mesma coluna, e mesma diagonal, que é Math.Abs(col[r] - c) == row - r.

Não há um passo de desfazer explícito, e o comentário diz por quê: col[row] é sobrescrito na próxima iteração, e nada na linha atual ou abaixo dela é lido de novo. Quando o passo de desfazer não faz nada, vale um comentário dizendo isso — senão o próximo leitor assume que foi esquecido.

Custo: bem melhor que os 256 arranjos que a força bruta testaria, e ainda assim exponencial.

Use quando o problema é um quebra-cabeça de restrições — Sudoku, caça-palavras, coloração de grafos. Codificar uma restrição na forma da recursão em vez de testá-la é a jogada a procurar sempre.

O que lembrar

  • Escolher, explorar, desfazer. O passo de desfazer é o que as pessoas esquecem, e o código parece completo sem ele.

  • Copie o estado quando registrar. [.. current] — senão todo resultado aponta para uma lista só, que acaba vazia.

  • Subconjuntos são registrados em cada nó, não nas folhas. O Add vai antes do laço.

  • Confira se o estado voltou ao original no fim. Um array de permutação de volta à ordem original prova que os desfazeres se equilibraram.

  • Ordene antes de podar, e use break em vez de continue. Assim que um candidato é grande demais, numa lista ordenada todos são.

  • i reusa um candidato; start evita duplicatas reordenadas. Duas decisões de índice diferentes que é fácil confundir.

  • O pulo de duplicatas é i > start, não i > 0. Contra start, para que o mesmo valor ainda possa ser a primeira escolha num nível mais fundo.

  • Coloque as restrições na forma da recursão quando der. Uma linha por chamada faz a regra da linha não precisar de código nenhum.

A parte 16 é a última: manipulação de bits, que a série vem usando desde a parte 3 sem nunca dizer isso em voz alta.

How useful was this post?

Click on a heart to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.