Saltar al contenido

Elegir k de los primeros n números

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

La misión

Problema

Dados dos enteros n y k, devuelve todas las formas de elegir k números distintos entre 1 y n. El orden dentro de una elección no importa, así que escribe cada elección en orden ascendente, y devuelve las elecciones en orden lexicográfico ascendente.

Ejemplos

Input:  n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Por qué: las combinaciones de 4 elementos tomados de 2 en 2 son 6
Input:  n = 3, k = 3
Output: [[1, 2, 3]]
Por qué: solo hay una forma de tomarlos todos
Input:  n = 2, k = 0
Output: [[]]
Por qué: caso límite: no elegir nada es exactamente una elección, la vacía

Pistas

0 / 3

Tiempo objetivo
O(k · C(n, k))
Espacio objetivo
O(k · C(n, k))

¿Lo que te frena es la idea y no el código? Subconjuntos lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio