backtracking

Backtracking (orqaga qaytish) — javobni qadamma-qadam quramiz; yo‘l noto‘g‘ri bo‘lib chiqsa, oxirgi tanlovni bekor qilib, boshqasini sinaymiz. Bu aqlli to‘liq perebor.

def subsets(nums):
    result, cur = [], []

    def go(i):
        if i == len(nums):
            result.append(cur[:])
            return
        go(i + 1)              # nums[i] ni olmaymiz
        cur.append(nums[i])    # olamiz
        go(i + 1)
        cur.pop()              # bekor qilamiz — orqaga qaytish

    go(0)
    return result

Klassik masalalar

• Barcha qism to‘plamlar, perestanovkalar, kombinatsiyalar.
• N ta farzin (queen), sudoku, labirintdan barcha yo‘llar.

Kesish (pruning)

Javob bo‘lishi mumkin bo‘lmagan shoxni erta to‘xtating: masalan, yig‘indi allaqachon chegaradan oshgan bo‘lsa, chuqurroq kirmang. Bu vaqtni ko‘p marta qisqartiradi.