Pular para o conteúdo

Escolher K dos N primeiros números

Fácil#backtracking#combinations#pruning~15 min

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

Tempo-alvo
O(k · C(n, k))
Espaço-alvo
O(k · C(n, k))

Travou na ideia, e não no código? Subconjuntos explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado