Pular para o conteúdo

Arranjos de dígitos até um limite

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

A missão

Problema

Dada uma lista de dígitos distintos e um limite, retorne, em ordem crescente, todos os números que usam cada dígito exatamente uma vez, em alguma ordem, e que não passam do limite. Um número não pode começar com 0, a menos que seja o dígito único 0. Há no máximo 8 dígitos.

Exemplos

Input:  digits = [3, 1, 2], limit = 300
Output: [123, 132, 213, 231]
Por quê: 312 e 321 passam do limite, e tentar os dígitos em ordem crescente já gera os números ordenados
Input:  digits = [0, 2, 1], limit = 999
Output: [102, 120, 201, 210]
Por quê: arranjos que começam com 0 são pulados, porque 012 na verdade é um número de dois dígitos
Input:  digits = [5], limit = 4
Output: []
Por quê: edge case: o único arranjo já passa do limite

Dicas

0 / 3

Tempo-alvo
O(n · n!)
Espaço-alvo
O(n!)

Restrições

  • digits are distinct
  • at most 8 digits

Travou na ideia, e não no código? Permutações explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado