Escolher K dos N primeiros números
A missão
Problema
Dados dois inteiros n e k, retorne todas as formas de escolher k números diferentes de 1 a n. A ordem dentro de uma escolha não importa, então escreva cada escolha em ordem crescente e retorne as escolhas em ordem lexicográfica crescente.
Exemplos
Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Por quê: a combinação de 4 tomados 2 a 2 é 6
Input: n = 3, k = 3
Output: [[1, 2, 3]]
Por quê: só existe uma forma de pegar tudo
Input: n = 2, k = 0
Output: [[]]
Por quê: edge case: não escolher nada é exatamente uma escolha, a vazia
Dicas
0 / 3
Monte uma escolha um número por vez. Para manter cada escolha em ordem crescente e não produzir [2, 1] depois de [1, 2], só adicione números maiores que o último que você adicionou.
Faça a recursão com um valor inicial: escolha um número x a partir de start, chame recursivamente com start x + 1, depois remova x e tente o próximo. Registre uma cópia quando a escolha tiver k números.
Faça a poda no loop: se você ainda precisa de m números, começar em x só funciona quando x + m - 1 <= n, então o loop pode parar em n - m + 1 em vez de n.
- Tempo-alvo
- O(k · C(n, k))
- Espaço-alvo
- O(k · C(n, k))
Solução
Esta é a árvore de decisão dos subconjuntos, cortada na profundidade k. Cada nível decide o próximo número da escolha, e passar x + 1 como o próximo início garante que toda escolha seja montada em ordem crescente; assim, cada grupo de números é produzido exatamente uma vez e a saída já sai em ordem lexicográfica. Depois que a chamada recursiva retorna, o número é removido, o que devolve a lista compartilhada pick ao estado em que o loop a encontrou. O limite superior do loop é o passo de poda (pruning): um ramo que não tem como juntar números suficientes nunca é explorado. Há C(n, k) escolhas e cada uma custa O(k) para ser copiada, então o tempo é O(k × C(n, k)) e a profundidade da recursão é k.
def choose(n, k):
out, pick = [], []
def build(start):
if len(pick) == k:
out.append(pick[:]) # record a copy, pick keeps changing
return
need = k - len(pick)
for x in range(start, n - need + 2): # leave room for the numbers still needed
pick.append(x)
build(x + 1)
pick.pop() # undo before trying the next x
build(1)
return out
print(choose(4, 2)) # -> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
print(choose(3, 3)) # -> [[1, 2, 3]]
print(choose(2, 0)) # -> [[]]Travou na ideia, e não no código? Subconjuntos explica isso.