Saltar al contenido

Permutaciones de dígitos hasta un límite

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

La misión

Problema

Dada una lista de dígitos distintos y un límite, devuelve en orden creciente todos los números que usan cada dígito exactamente una vez, en algún orden, y que no superan el límite. Un número no puede empezar con 0 salvo que sea el dígito 0 solo. Hay como máximo 8 dígitos.

Ejemplos

Input:  digits = [3, 1, 2], limit = 300
Output: [123, 132, 213, 231]
Por qué: 312 y 321 superan el límite, y probar los dígitos en orden creciente produce los números ya ordenados
Input:  digits = [0, 2, 1], limit = 999
Output: [102, 120, 201, 210]
Por qué: se descartan los órdenes que empiezan con 0, porque 012 es en realidad un número de dos dígitos
Input:  digits = [5], limit = 4
Output: []
Por qué: caso límite: el único orden posible ya supera el límite

Pistas

0 / 3

Tiempo objetivo
O(n · n!)
Espacio objetivo
O(n!)

Restricciones

  • digits are distinct
  • at most 8 digits

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

Python 3Ctrl+Enter ejecuta
Caso de prueba propio