Alt Kümeler

Geri İzleme O(2^n) O(n)

Her eleman için alma ya da dışarıda bırakma diye dallanarak bir kümenin tüm alt kümelerini üretir.

oluşturuluyor

{1}

kaydedilen (0)

henüz yok

Küme: 1, 2, 3 · 0 / 8 bulundu

1/22

1 dahil ediliyor.

DeğişmezMevcut liste, ilk i eleman için verilmiş bir karardır: içinde ya da dışında.

seçgeri izlemekaydedildi

subsets.c

void subsets(int a[], int n, int i, int cur[], int k) {
    if (i == n) {
        printSubset(cur, k);
        return;
    }
    cur[k] = a[i];              /* include a[i] */
    subsets(a, n, i + 1, cur, k + 1);
    /* backtrack: exclude a[i] */
    subsets(a, n, i + 1, cur, k);
}

Alt Kümeler nasıl çalışır?

Her eleman için ikili karar ver: içeride mi dışarıda mı. Özyineleme ağacının 2ⁿ yaprağı vardır — her yaprak tam olarak bir alt kümedir.

Ne zaman kullanılır?

Kaba kuvvet kontrolleri, kuvvet kümeleri, öznitelik alt kümeleri için tüm kombinasyonları sayma.