Backtracking (geri izləmə) sistemli axtarışdır: həll bir-bir seçimlərlə qurulur, yarımçıq həll uğura aparmayanda isə bir addım geri qayıdıb növbəti variantı yoxlayırıq. Bu, qərar ağacının dərinlik üzrə gəzilməsidir.

Şablon: seç, araşdır, ləğv et

Üç elementli çoxluğun alt çoxluqlarının qərar ağacı: hər səviyyədə götür və ya burax
Üç elementli çoxluğun alt çoxluqlarının qərar ağacı: hər səviyyədə götür və ya burax

Bir dəyişən path saxlanılır. Hər addımda:

  1. seç: path-ə element əlavə et;
  2. araşdır: qalan hissə üçün rekursiv çağır;
  3. ləğv et: elementi çıxar ki, növbəti seçim təmiz vəziyyətdən başlasın.

path tamamlananda onun surətini (path[:]) saxlayırıq, çünki eyni siyahı sonradan dəyişməyə davam edir.

Alt çoxluqlar: 2^n yarpaq

Hər element üçün iki budaq var: burax və ya götür. n elementli çoxluğun 2^n alt çoxluğu olur.

python
def subsets(items):
    result, path = [], []

    def explore(i):
        if i == len(items):
            result.append(path[:])
            return
        explore(i + 1)           # branch 1: skip items[i]
        path.append(items[i])    # choose
        explore(i + 1)           # branch 2: take items[i]
        path.pop()               # undo

    explore(0)
    return result