İçeriğe geç

Alt kümeler

Ders 2 / 5 · 5 dk

Alt kümeler

Adım 1/7

Alt küme, her eleman için bir evet ya da hayır cevabıdır; yani ağacın her seviyesinde tam iki dal var.

Fikir

Alt küme, her öğe için tek bir evet/hayır cevabıdır; bu yüzden karar ağacı ikilidir: nums[i]'yi atla ya da al ve devam et.

İndeks hep ileri gider; {1, 2} ile {2, 1}'in ikisinin birden çıkmasını engelleyen de bu. Her yaprak, bütün kararların verildiği bir uçtur; bu yüzden tam olarak 2 üzeri n yaprak vardır. Ortak yolu temiz tutan da yine al dalından sonraki pop.

Gerçek hayattan örnek

Bir build için hangi opsiyonel modüllerin açılacağını seçtiğini düşün. Her flag bağımsız ve release ekibi her kombinasyonun test edilmesini istiyor: üç flag için sekiz build, dört flag için on altı.

Kod

Sıra sende

Bu kod ne yazdırır?

out = []
subsets([1, 2, 3], 0, [], out)
print(len(out))

Mini quiz

1 / 3

n öğe için alt küme ağacının kaç yaprağı olur?