Escreva uma função recursiva que gere todas as possíveis combinações para um jogo da MegaSena com 6 dezenas

Passo 1

O problema pede uma função recursiva que gere todas as combinações de 6 dezenas distintas escolhidas dentre os números de 1 a 60 (MegaSena). O conteúdo principal aqui é backtracking ou geração de combinações via recursão, mantendo uma lista temporária com a combinação atual e avançando até ter 6 elementos.

Passo 2

A ideia é percorrer sequencialmente a lista de números disponíveis, numa chamada recursiva que:
1. Adiciona o número atual à combinação temporária.
2. Se a combinação temporária atingir tamanho 6, copia-a ao resultado.
3. Caso contrário, faz recursão a partir do próximo índice.
4. Após voltar da recursão, remove o último número (backtracking) e continua com o próximo.

Passo 3

Definimos:
  • source: lista de inteiros de 1 a 60.
  • k: tamanho da combinação (aqui \(6\)).
  • comb: lista temporária que armazena a combinação em construção.
  • resultado: lista que acumula todas as combinações finais.
  • A função interna backtrack(start) tenta incluir cada elemento de índice i em comb, com i variando de start até o final de source.

Passo 4

A implementação em Python fica assim:
def \(gerar_combinacoes\)(source, k):
    resultado \(=\) []
    comb \(=\) []
    def backtrack(start):
        # Se atingimos k elementos, gravamos uma cópia da combinação
        if len(comb) \(==\) k:
            resultado.append(comb.copy())
            return
        # Tentar cada índice a partir de 'start'
        for i in range(start, len(source)):
            comb.append(source[i])
            backtrack(i \(+1\))
            comb.pop()  # desfaz a escolha para tentar o próximo
    backtrack(\(0\))
    return resultado

# Exemplo de uso:
numeros \(=\) list(range(\(1\), \(61\)))
combinacoes \(= gerar_combinacoes\)(numeros, \(6\))
# Isso produzirá uma lista com C(\(60,6\)) combinações

Resposta

def \(gerar_combinacoes\)(source, k):
    resultado \(=\) []
    comb \(=\) []
    def backtrack(start):
        if len(comb) \(==\) k:
            resultado.append(comb.copy())
            return
        for i in range(start, len(source)):
            comb.append(source[i])
            backtrack(i \(+1\))
            comb.pop()
    backtrack(\(0\))
    return resultado

# Para MegaSena:
numeros \(=\) list(range(\(1\), \(61\)))
combinacoes \(= gerar_combinacoes\)(numeros, \(6\))

Exercícios relacionados