İçeriğe geç

İlk n sayıdan k tanesini seç

Kolay#backtracking#combinations#pruning~15 dk

Görev tanımı

Problem

İki tam sayı n ve k verildiğinde, 1 ile n arasından k farklı sayı seçmenin her yolunu döndür. Bir seçimin içindeki sıra önemli değil; bu yüzden her seçimi artan sırada yaz ve seçimleri artan sözlük sırasıyla döndür.

Örnekler

Input:  n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Neden: 4'ün 2'li kombinasyonu 6
Input:  n = 3, k = 3
Output: [[1, 2, 3]]
Neden: hepsini almanın tek bir yolu var
Input:  n = 2, k = 0
Output: [[]]
Neden: edge case: hiçbir şey seçmemek tam olarak bir seçimdir, boş seçim

İpuçları

0 / 3

Hedef zaman
O(k · C(n, k))
Hedef alan
O(k · C(n, k))

Kodda değil de fikirde mi takıldın? Alt kümeler bunu anlatıyor.

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