Na maioria dos casos, os problemas de enumeração são resolvidos por enumeração recursiva. Infelizmente, não há uma abordagem geral, porque muitas vezes, os métodos de iteração são altamente dependentes da própria tarefa.
No entanto, pode-se notar alguma semelhança entre os métodos de enumeração de vários objetos combinatórios. Portanto, para um exemplo ilustrativo, considere um código que gera todas as combinações de n a k.
int n, k;
// Uma matriz que suporta prefixos de combinação.
//
// O prefixo neste caso significa que selecionamos alguns objetos na combinação.
//
// Posteriormente, eles serão concluídos na combinação correta,
// ou a recursão cortará a ramificação quando perceber que tal prefixo não pode ser completado corretamente
vetor arr;
// a própria função de iteração recursiva
//
// pos - número do objeto em combinação, que determinaremos no momento atual (de 0 a k - 1)
//
// prev - o valor do objeto que foi obtido na etapa anterior
//
// Em combinações, a ordem dos objetos não é importante ([1, 2] e [2, 1] são considerados iguais e semelhantes),
// então queremos apenas gerar conjuntos onde os valores dos objetos estão em ordem crescente.
//
// Isso é necessário para que as mesmas opções como [1, 2] e [2, 1] sejam iteradas apenas uma vez
// (no nosso caso, vamos considerar apenas [1, 2], mas não [2, 1], pois não é um conjunto ordenado).
//
// É por isso que mantemos a variável prev para reduzir o número de iterações
void rec(int pos, int anterior) {
// se o número do elemento selecionado for igual a k, então já selecionamos todos os elementos
// porque seus números são de 0 a k - 1
if (pos == k) {
// se a condição for atendida, então a combinação correta está agora no array arr
// e podemos processá-lo de alguma forma (neste caso, basta imprimir no console)
para (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
retornar; // corta o ramo de recursão, porque já tenho uma combinação e não há necessidade de continuar
}
// aqui verificamos se podemos obter a combinação correta dos elementos restantes
// se não houver elementos restantes suficientes, cortamos esse ramo de recursão
se (k - pos > n - anterior - 1)
retornar;
// iteramos sobre o objeto que colocamos na posição com índice pos
// mas porque queremos um conjunto ordenado, então o valor mínimo possível é anterior + 1
for (int i = anterior + 1; i < n; i++) {
arr.push_back(i); // Adiciona um elemento ao array global. Agora parece que o escolhemos
rec(pos + 1, i); // executa recursivamente para definir os seguintes itens
arr.pop_back(); // depois de retornar da recursão, nosso elemento atualmente selecionado não é mais relevante,
// porque dentro da recursão, passamos por todas as opções com tal prefixo,
// então este elemento precisa ser removido
}
}
int main()
{
cin>> n>> k;
// inicialmente vamos definir o elemento na posição 0
// assumimos que o elemento -1 foi selecionado antes, de modo que a iteração começa inicialmente a partir de um objeto nulo
rec(0, -1);
retorna 0;
}
O mesmo código, mas sem comentários:
int n, k;
vetor arr;
void rec(int pos, int anterior) {
if (pos == k) {
para (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
retornar;
}
se (k - pos > n - anterior - 1)
retornar;
for (int i = anterior + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, i);
arr.pop_back();
}
}
int principal() {
cin>> n>> k;
rec(0, -1);
retorna 0;
}
Em iterações recursivas, atenção especial sempre deve ser dada aos cortes de recursão. Na prática, eles podem acelerar bastante o programa.