İçeriğe geç

Sınırı aşmayan rakam dizilimleri

Kolay#backtracking#permutations#pruning~15 dk

Görev tanımı

Problem

Birbirinden farklı rakamlardan oluşan bir liste ve bir sınır verildiğinde, her rakamı bir sırayla tam bir kez kullanan ve en fazla sınır kadar olan her sayıyı artan sırada döndür. Bir sayı, tek basamaklı 0 değilse 0 ile başlayamaz. En fazla 8 rakam var.

Örnekler

Input:  digits = [3, 1, 2], limit = 300
Output: [123, 132, 213, 231]
Neden: 312 ve 321 sınırı aşıyor; rakamları artan sırada denemek sayıları zaten sıralı verir
Input:  digits = [0, 2, 1], limit = 999
Output: [102, 120, 201, 210]
Neden: 0 ile başlayan dizilimler atlanır, çünkü 012 aslında iki basamaklı bir sayıdır
Input:  digits = [5], limit = 4
Output: []
Neden: edge case: tek dizilim zaten sınırı aşıyor

İpuçları

0 / 3

Hedef zaman
O(n · n!)
Hedef alan
O(n!)

Kısıtlar

  • digits are distinct
  • at most 8 digits

Kodda değil de fikirde mi takıldın? Permütasyonlar bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case