Dados dois inteiros n e k, retorne todas as possíveis combinações de k números dentro do intervalo [1, n]. As combinações podem ser retornadas em qualquer ordem.

Abordagem Inicial

Vamos considerar n=4 e k=2. Uma primeira abordagem seria utilizar laços for aninhados:

for (int i=1; i<=4; ++i) {
  for (int j=i+1; j<=4; ++j) {
    // Armazenar resultado
  }
}

Essa abordagem funciona para valores fixos de n e k, mas quando k é variável, precisaríamos de k laços for aninhados, o que não é escalável. Essa limitação nos leva ao algoritmo de backtracknig, que pode ser visto como laços for dinamicamente aninhados.

Conceito do Algoritmo de Backtracking

O algoritmo de backtracking segue uma abordagem passo a passo:

1. Gerar uma árvore de backtracking com base no problema
2. Implementar o algoritmo de backrtacking correspondente:
   • Determinar os parâmetros e tipo de retorno
   • Definir as condições de parada da recursão
   • Estruturar a lógica do laço único

Como as combinações não consideram a ordem dos elementos (1,2) é equivalente a (2,1), cada número só pode ser combinado com números maiores que ele. Isso evita combinações duplicadas.

Exemplo com Backtracking

Para n=4 e k=2:

• O número 1 pode ser combinado com 2, 3 e 4
• O número 2 pode ser combinado com 3 e 4
• O número 3 pode ser combinado com 4

Essas relações formam nossa árvore de backtracking.

Implementação do Algroitmo

a. Tipo de retorno e parâmetros:

O método principal retornará uma lista de listas de inteiros. Os parâmetros incluem n, k e o ponto de partida para evitar combinações duplicadas.

b. Condição de parada:

A recursão para quando o tamanho da combinação atual atinge k.

c. Lógica do laço único:

Iteramos a partir do índice atual até n, adicionando cada número à combinação atual e chamando recursivamente a função com o próximo índice.

Código Implementado

import java.util.ArrayList;
import java.util.List;

public class SolucaoCombinacoes {
    private List<list>> saida = new ArrayList<>();
    private List<integer> caminho = new ArrayList<>();
    
    public List<list>> combinar(int n, int k) {
        backtracking(n, k, 1);
        return saida;
    }
    
    private void backtracking(int n, int k, int inicio) {
        // Condição de parada: quando o caminho tem tamanho k
        if (caminho.size() == k) {
            saida.add(new ArrayList<>(caminho));
            return;
        }
        
        // Laço para explorar todas as possibilidades
        for (int i = inicio; i <= n; i++) {
            // Adicionar número atual ao caminho
            caminho.add(i);
            
            // Chamada recursiva com próximo índice
            backtracking(n, k, i + 1);
            
            // Remover último elemento (backtrack)
            caminho.remove(caminho.size() - 1);
        }
    }
}
</list></integer></list>