Backtracking asoslari: qism-to'plam, permutatsiya va kombinatsiya

Qisqacha: Backtracking (orqaga qaytish) — hamma variantni tartibli sinash usuli: bitta tanlov qilasiz, shu tanlov bilan chuqurga tushasiz (rekursiya), qaytgach tanlovni bekor qilasiz va keyingisini sinaysiz. Hamma tanlovlar ketma-ketligi holat daraxtini hosil qiladi. Uchta klassik masala bitta qolipdan chiqadi: qism-to'plamlar (2ⁿ ta), permutatsiyalar (n! ta) va k talik kombinatsiyalar (C(n, k) ta). Javoblar soni shunchalik tez o'sadiki, backtracking faqat kichik n da (20 atrofigacha) amaliy.

Bu darsda

• "Tanla → chuqurga tush → bekor qil" qolipini va holat daraxtini tushuntira olasiz.
• Qism-to'plamlar, permutatsiyalar va kombinatsiyalarni bitta qolipdan yoza olasiz.
• Javoblar sonini (2ⁿ, n!, C(n, k)) hisoblab, qaysi n gacha backtracking amaliy ekanini baholay olasiz.
• Nusxa olishni unutish va takroriy elementlar kabi tuzoqlardan qochasiz.

Oldin bilishingiz kerak: Rekursiv fikrlash, Asosiy murakkablik sinflari, Stack (LIFO).

1. Nega bu kerak?

«Bahor» da uchta yangi savol paydo bo'ldi.

Jasur aka kombo taklif qilmoqchi: asosiy taomga qo'shimchalar — non, salat, choy. Mehmon ulardan istaganini oladi yoki hech birini olmaydi. Kassa dasturida hamma variant tugma bo'lishi kerak. Nechta va qaysilar?

Kuryer uch manzilga — Chilonzor, Yunusobod va Sergeliga — buyurtma eltadi. Qaysi tartibda yursa yo'l eng qisqa bo'ladi? Buni bilish uchun avval hamma tartiblarni sanab chiqish kerak.

Banket uchun beshta salatdan uchtasini tanlash kerak. Qanday uchliklar bor?

Uchala savolda ham javob — "hamma variantlar ro'yxati". Rekursiv fikrlash darsida masalani kichik nusxasiga bo'lishni o'rgandik. Bugun rekursiyaga yana bitta g'oya qo'shamiz: tanlovni bekor qilish. Natija — backtracking, hamma variantni sinashning universal usuli.

2. Sodda yechim va uning chegarasi

Uch qo'shimchali kombo uchun ichma-ich uchta sikl yozish mumkin: har qo'shimcha uchun "olaman / olmayman":

const extras = ["non", "salat", "choy"];
const combos = [];
for (const takeBread of [false, true]) {
  for (const takeSalad of [false, true]) {
    for (const takeTea of [false, true]) {
      const combo = [];
      if (takeBread) combo.push(extras[0]);
      if (takeSalad) combo.push(extras[1]);
      if (takeTea) combo.push(extras[2]);
      combos.push(combo.join("+") || "—");
    }
  }
}
console.log(combos.length); // 8
console.log(combos.join(" | "));

Konsolda:

8
— | choy | salat | salat+choy | non | non+choy | non+salat | non+salat+choy

Ishlaydi — lekin faqat aynan uchta qo'shimcha uchun. To'rtinchi qo'shimcha — to'rtinchi sikl, kod o'zgaradi. O'tgan darsdagi menyu qavatlari muammosi bilan bir xil: siklar soni ma'lumotga bog'liq bo'lsa, rekursiya kerak.

3. Backtracking qolipi

3.1 Uch harakat

Backtracking har qadamda uchta ishni qiladi:

1. Tanla — joriy holatga bitta element qo'shish (current.push(x)).
2. Chuqurga tush — shu tanlov bilan qolgan qismini rekursiv hal qilish.
3. Bekor qil — qaytgach, tanlovni olib tashlash (current.pop()), toki holat tanlovdan oldingi ko'rinishga qaytsin va keyingi variantni toza holatdan sinash mumkin bo'lsin.

O'xshatish: labirintda yo'l qidiryapsiz. Har chorrahada bitta yo'lni tanlaysiz va ichkariga kirasiz. Boshi berk ko'chaga chiqsangiz — chorrahaga qaytasiz va keyingi yo'lni sinaysiz. "Orqaga qaytish" — backtracking so'zining tarjimasi aynan shu.

Har chaqiruv ichidagi aylanani sxemada ko'ring — har chorrahada shu uch harakat takrorlanadi:

flowchart TD
  A["Joriy holat: current"] --> B{"Sinalmagan tanlov bormi?"}
  B -- "ha" --> C["Tanla: current.push(x)"]
  C --> D["Chuqurga tush: backtrack()"]
  D --> E["Bekor qil: current.pop()"]
  E --> B
  B -- "yo'q" --> F["Oldingi chorrahaga qayt"]

Uchinchi harakat — butun usulning yuragi. Barcha shoxlar bitta current massividan foydalanadi. Har shox ishini tugatgach uni o'zidan oldingi holatga qaytarmasa, keyingi shox "iflos" holatdan boshlaydi.

3.2 Holat daraxti

Har tanlovlar ketma-ketligi — daraxtdagi bitta yo'l. Ildiz — hali hech narsa tanlanmagan holat. Har tugunning bolalari — undan keyingi mumkin bo'lgan tanlovlar. Bu holat daraxti (state space tree). Backtracking uni chuqurlik bo'yicha aylanadi: avval bitta shoxning oxirigacha tushadi, keyin qaytib, keyingisiga o'tadi.

O'tgan darsdagi rekursiya daraxti bilan farqi: bu yerda daraxt ma'lumotda yo'q — u tanlovlardan yasaladi. Shuning uchun u juda tez kattalashadi.

4. Qism-to'plamlar

4.1 Kod va daraxt

Qism-to'plam (subset) — to'plamdan istalgan elementlarni olish natijasi, bo'shi va to'liqi bilan birga. Kombo variantlari — aynan qo'shimchalarning qism-to'plamlari.

Qolip: backtrack(start) — start dan o'ngdagi elementlardan birini tanlab qo'shadi. Har holat (har tugun) — bitta javob, shuning uchun natijaga har chaqiruvda yoziladi. start dan chapga qaytilmaydi — shu tufayli {non, salat} va {salat, non} ikki marta chiqmaydi. Daraxt va current massivini kuzating:

Nimaga qarang. current — butun jarayonda bitta massiv: tanlovda o'sadi, bekor qilishda qisqaradi. Natijaga esa uning nusxasi ([...current]) yoziladi — nega bu muhimligini "Ko'p uchraydigan xatolar" bo'limida ko'ramiz.

4.2 Nechta?

Har element uchun ikki yo'l: olish yoki olmaslik. n ta element — 2 × 2 × … × 2 = 2ⁿ ta qism-to'plam. Har birini nusxalash O(n) — jami O(n · 2ⁿ) vaqt. Xotira: natijadan tashqari, stek chuqurligi va current — O(n).

Tekshirib ko'ring: Qo'shimchalar beshta bo'lsa, kombo variantlari (bo'sh kombo bilan) nechta?

5. Permutatsiyalar

5.1 Tartib muhim bo'lsa

Kuryer masalasida tartib muhim: Chilonzor → Yunusobod va Yunusobod → Chilonzor — boshqa-boshqa yo'l. Permutatsiya (permutation) — hamma elementlarning qandaydir tartibi. Endi start yetmaydi: har qadamda hali ishlatilmagan istalgan elementni tanlash mumkin, chapdagisini ham. Qaysi elementlar band ekanini used massivida eslab boramiz.

Javob — faqat to'liq yo'l. Daraxtda u barg (leaf) bo'ladi: bolasi yo'q, eng pastdagi tugun — xuddi shoxning uchidagi barg kabi. Shuning uchun natijaga faqat current uzunligi n ga yetganda yoziladi. Manzillar qisqartirilgan: Ch — Chilonzor, Yu — Yunusobod, Se — Sergeli. Yuqoridagi massivda xira katak — allaqachon yo'ldagi manzil:

5.2 Nechta?

Birinchi manzilga n ta tanlov, ikkinchisiga n − 1, … oxirgisiga 1. Jami n! ta tartib. Faktorial (factorial) — 1 dan n gacha sonlar ko'paytmasi, "en faktorial" deb o'qiladi: 3! = 3 · 2 · 1 = 6, 4! = 24. Har birini nusxalash O(n) — O(n · n!) vaqt. Bu Asosiy murakkablik sinflari darsidagi eng tez o'suvchi sinf.

Kuryer uchun bu nimani anglatadi? 10 ta manzilda — 3 628 800 yo'l. Kompyuter buni soniyadan kamroqda sanab chiqadi. 15 ta manzilda — 1,3 trillion: kunlar ketadi. "Eng qisqa yo'l" masalasini hamma tartiblarni sinamasdan yechish usullari — Eng qisqa yo'l va Dinamik dasturlash darslarida.

Tekshirib ko'ring: Permutatsiya daraxtida 3 ta manzil uchun 16 ta tugun bor edi: ildiz, 3, 6 va 6. Qism-to'plamlar daraxtida esa javoblar va tugunlar soni bir xil (8 ta). Nega permutatsiyada tugunlar javoblardan ko'p?

6. Kombinatsiyalar

6.1 k tasini tanlash

Banket salatlari: beshtadan aynan uchtasi, tartib muhim emas. Bu — kombinatsiya (combination). Qolip qism-to'plamlar bilan bir xil (start bilan, tartib takrorlanmasin), faqat natijaga k ta tanlanganda yoziladi va chuqurga tushish to'xtaydi:

function combinations(items, k) {
  const result = [];
  const current = [];
  function backtrack(start) {
    if (current.length === k) {
      result.push([...current]); // k ta tanlandi — tayyor
      return;
    }
    for (let i = start; i < items.length; i++) {
      current.push(items[i]);
      backtrack(i + 1); // faqat o'ngdagilardan: tartib takrorlanmaydi
      current.pop();
    }
  }
  backtrack(0);
  return result;
}

const salads = ["vinegret", "olivye", "sezar", "mimoza", "achchiq"];
const sets = combinations(salads, 3);
console.log(sets.length); // 10
console.log(sets[0].join(", ")); // vinegret, olivye, sezar
console.log(sets.at(-1).join(", ")); // sezar, mimoza, achchiq

Kombinatsiya daraxti — qism-to'plamlar daraxtining o'zi, faqat k-qavatda kesilgan. Qism-to'plamlar daraxtida har tugun javob edi. Bu yerda esa faqat aynan k ta tanlangan tugunlar javob, undan chuqurga tushilmaydi. Ikki qolip orasidagi farq — bitta if.

Endi o'zingiz sanang. To'rtta salatdan ikkitasini tanlash: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. Demak, C(4, 2) = .

6.2 Nechta?

n tadan k tasini tanlashlar soni C(n, k) deb yoziladi va "n dan k" deb o'qiladi. Formulasi: C(n, k) = n! ÷ (k! · (n − k)!). Formulani yodlash shart emas — mantig'i muhim. Beshtadan uchtasi: 120 ÷ (6 · 2) = 10. Tartib muhim bo'lganida 5 · 4 · 3 = 60 bo'lardi; har uchlik 3! = 6 xil tartibda takrorlanadi, 60 ÷ 6 = 10.

Uch masalani bitta jadvalda solishtiramiz:

function factorial(n) {
  return n <= 1 ? 1 : n * factorial(n - 1);
}
function choose(n, k) {
  return factorial(n) / (factorial(k) * factorial(n - k));
}

for (const n of [3, 5, 10, 15, 20]) {
  const counts = `2ⁿ=${2 ** n}, n!=${factorial(n)}`;
  console.log(`n=${n}: ${counts}, C(n,3)=${choose(n, 3)}`);
}

Konsolda:

n=3: 2ⁿ=8, n!=6, C(n,3)=1
n=5: 2ⁿ=32, n!=120, C(n,3)=10
n=10: 2ⁿ=1024, n!=3628800, C(n,3)=120
n=15: 2ⁿ=32768, n!=1307674368000, C(n,3)=455
n=20: 2ⁿ=1048576, n!=2432902008176640000, C(n,3)=1140

C(n, 3) sekin o'sadi — u taxminan n³ ÷ 6, ya'ni ko'phadli. 2ⁿ va n! esa portlaydi. 20! allaqachon Number.MAX_SAFE_INTEGER dan katta — aniq hisob kerak bo'lsa, BigInt kerak bo'ladi.

Tekshirib ko'ring: Kombinatsiya kodida backtrack(i + 1) o'rniga backtrack(0) yozilsa nima bo'ladi?

7. Boshqa yo'llar: bitmask va generator

7.1 Bitmask bilan qism-to'plamlar

Qism-to'plamlarni rekursiyasiz ham yasash mumkin. n ta elementning har qism-to'plami — n bitli son: i-bit 1 bo'lsa, i-element olinadi (Bit manipulyatsiya masalalari). 0 dan 2ⁿ − 1 gacha sanab chiqsak — hamma qism-to'plamlar:

const extras = ["non", "salat", "choy"];
const combos = [];
for (let mask = 0; mask < 1 << extras.length; mask++) {
  // i-bit yoqilgan bo'lsa — i-qo'shimcha kombo ichida
  const combo = extras.filter((_, i) => mask & (1 << i));
  combos.push(combo.join("+") || "—");
}
console.log(combos.join(" | "));

Konsolda:

— | non | salat | non+salat | choy | non+choy | salat+choy | non+salat+choy

1 << n — 2ⁿ, mask & (1 << i) — "i-bit yoqilganmi?". Kod qisqa va stek ishlatmaydi. Lekin u faqat qism-to'plamlarga mos: permutatsiyalarni yoki "byudjetdan oshdi — bu shoxni tashla" kabi qarorlarni bunday yozib bo'lmaydi. Backtracking qolipi esa hammasiga moslashadi.

7.2 Javoblarni birma-bir berish: generator

Odatda bizga hamma javob kerak emas — shartga mos birinchisi yetadi. Masalan, narxi aynan 16 000 so'm bo'lgan birinchi kombo. Hammasini massivga yig'ib, keyin qidirish — ortiqcha ish va xotira. Generator funksiya javoblarni bittalab beradi: keyingisi faqat so'ralganda yasaladi.

function* subsetsLazy(items, start = 0, current = []) {
  yield [...current];
  for (let i = start; i < items.length; i++) {
    current.push(items[i]);
    yield* subsetsLazy(items, i + 1, current); // ichki javoblar ham
    current.pop();
  }
}

const prices = new Map([
  ["non", 4000], ["salat", 12000], ["choy", 5000], ["kompot", 7000],
]);
let checked = 0;
for (const combo of subsetsLazy([...prices.keys()])) {
  checked++;
  const total = combo.reduce((s, x) => s + prices.get(x), 0);
  if (total === 16000) {
    console.log(combo.join("+"), `— ${checked}-variantda topildi`);
    break; // qolgan variantlar umuman yasalmaydi
  }
}

Konsolda:

non+salat — 3-variantda topildi

yield* ichki generatorning hamma javoblarini tashqariga uzatadi (yield*). break bilan sikl to'xtagach, generator ham to'xtaydi — qolgan 13 ta variant umuman yasalmadi. Katta qidiruvda bu farq soniyalar va gigabaytlarni tejaydi.

8. O'lchov: eksponensial va faktorial o'sish

Ikkala masalani javoblarni saqlamasdan, faqat sanab o'lchadik — aks holda vaqtning ko'pini xotira ajratish va axlat yig'ish oladi. Usul — benchmarking darsidagidek: har n alohida jarayonda, isitish, mediana:

Qism-to'plamlarda n bittaga oshganda vaqt aniq ≈ 2 baravar oshdi (16 → 17 → 18 → 19 → 20: ×1,98, ×2,02, ×1,99, ×1,97). Permutatsiyalarda — taxminan n + 1 baravar: 9 da ×9,7, 10 da ×10,7, 11 da ×12. 11 ta element uchun 2,7 soniya. Bashorat: 12 tada — taxminan yarim daqiqa, 13 tada — 7–8 daqiqa.

Javoblarni massivga saqlab ham o'lchadik. U holda 10 ta elementning permutatsiyalari 683 ms oldi — sanashdan 3 baravar sekin: 3,6 million massiv yaratiladi va xotira to'ladi. Agar hamma javob kerak bo'lmasa (masalan, faqat eng yaxshisi), ularni saqlamang — topgan zahoti tekshiring.

9. Chegaraviy holatlar

• Bo'sh ro'yxat. Qism-to'plamlar — [[]] (bitta bo'sh to'plam), permutatsiyalar — [[]] (bo'sh tartib), kombinatsiyalar k = 0 da — [[]]. Matematik jihatdan ham to'g'ri: 2⁰ = 0! = C(0, 0) = 1.
• k > n. Kombinatsiya yo'q — natija []. Bizning kod buni o'zi to'g'ri qaytaradi: current hech qachon k ga yetmaydi.
• Takroriy elementlar. ["osh", "choy", "osh"] — ikki "osh" turli indeksda, shuning uchun {osh} ikki marta chiqadi. Yechim: avval saralash (bir xillar yonma-yon tursin) va bitta qavatda bir xil elementni ikkinchi marta tanlamaslik:

function uniqueSubsets(items) {
  const sorted = items.toSorted(); // bir xillar yonma-yon
  const result = [];
  const current = [];
  function backtrack(start) {
    result.push(current.join("+") || "—");
    for (let i = start; i < sorted.length; i++) {
      // shu qavatda bir xil element ikkinchi marta tanlanmaydi
      if (i > start && sorted[i] === sorted[i - 1]) continue;
      current.push(sorted[i]);
      backtrack(i + 1);
      current.pop();
    }
  }
  backtrack(0);
  return result;
}

console.log(uniqueSubsets(["osh", "choy", "osh"]).join(" | "));

Konsolda:

— | choy | choy+osh | choy+osh+osh | osh | osh+osh

8 ta o'rniga 6 ta — takrorlar yo'q. i > start sharti muhim: u faqat bir qavatdagi takrorni to'xtatadi. Chuqurroq qavatda ikkinchi "osh" ni olish mumkin (osh+osh).

• Juda katta n. 25 ta elementning qism-to'plamlari — 33 million; 13 ta elementning permutatsiyalari — 6 milliard. Kod "osilib" qolgandek ko'rinadi. Oldindan javoblar sonini hisoblang.

10. Ko'p uchraydigan xatolar

10.1 Nusxa o'rniga havola

function subsetsBug(items) {
  const result = [];
  const current = [];
  function backtrack(start) {
    result.push(current); // ❌ nusxa emas — havola
    for (let i = start; i < items.length; i++) {
      current.push(items[i]);
      backtrack(i + 1);
      current.pop();
    }
  }
  backtrack(0);
  return result;
}

console.log(subsetsBug(["non", "choy"]));

Konsolda:

[ [], [], [], [] ]

To'rtta javob — hammasi bo'sh! result ga to'rt marta bitta massivga havola yozildi (Qiymat va havola). Oxirida current bo'sh — demak, hamma "javob" ham bo'sh. Tuzatish: result.push([...current]) — o'sha lahzadagi nusxa.

10.2 Bekor qilishni unutish

current.pop() (yoki used[i] = false) yo'q bo'lsa, tanlovlar to'planib boradi: ikkinchi shox birinchisining elementlari bilan boshlanadi. Tuzatish: har push ga — bitta pop, har used[i] = true ga — used[i] = false. Ular sikl ichida, rekursiv chaqiruvning ikki tomonida juft bo'lib tursin.

10.3 Permutatsiyada start ishlatish

Permutatsiya kodida start bilan sikl yozilsa, chapdagi elementlar hech qachon keyin kelmaydi — faqat bitta tartib chiqadi. Qoida: tartib muhim emas (qism-to'plam, kombinatsiya) — start; tartib muhim (permutatsiya) — used.

11. Mashqlar

1-mashq (oson): Sanab ko'ring

Kuryerga 4 ta manzil berildi. Barcha mumkin bo'lgan yo'llar (tartiblar) nechta?

2-mashq (o'rta): Byudjetga sig'adigan kombolar

Qo'shimchalar narxi: non 4 000, salat 12 000, choy 5 000, kompot 7 000, somsa 8 000. Narxi 20 000 so'mdan oshmaydigan bo'sh bo'lmagan kombolar nechta? Darsdagi subsets qolipidan foydalaning, narxlarni Map da saqlang (Map).

const prices = new Map([
  ["non", 4000], ["salat", 12000], ["choy", 5000],
  ["kompot", 7000], ["somsa", 8000],
]);

function subsets(items) {
  const result = [];
  const current = [];
  function backtrack(start) {
    result.push([...current]);
    for (let i = start; i < items.length; i++) {
      current.push(items[i]);
      backtrack(i + 1);
      current.pop();
    }
  }
  backtrack(0);
  return result;
}

const sum = (combo) => combo.reduce((s, x) => s + prices.get(x), 0);
const fits = subsets([...prices.keys()])
  .filter((combo) => combo.length > 0 && sum(combo) <= 20000);
console.log(fits.length); // 19

3-mashq (qiyin): Takrorsiz permutatsiyalar va testlar

kurs/mashqlar/14/24-backtracking/bt.test.mjs faylida uniquePermutations(items) ni yozing: takroriy elementlar bo'lsa ham har tartib bir marta chiqsin. Ishora: avval saralang; sikl ichida used[i] dan tashqari yana bitta shart — oldingi element bir xil va u hozir ishlatilmayotgan bo'lsa, o'tkazib yuboring. Testlar (node:test):

1. ["osh", "osh", "choy"] — 3 ta tartib.
2. Takrorsiz 4 ta element — 24 ta, hammasi turlicha.
3. Bo'sh ro'yxat — [[]].
4. combinations (darsdagi) 6 tadan 3 — 20 ta.

// kurs/mashqlar/14/24-backtracking/bt.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function uniquePermutations(items) {
  const sorted = items.toSorted();
  const result = [];
  const current = [];
  const used = new Array(sorted.length).fill(false);
  function backtrack() {
    if (current.length === sorted.length) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < sorted.length; i++) {
      if (used[i]) continue;
      // bir xil elementlar faqat chapdan o'ngga ketma-ket olinadi
      const same = i > 0 && sorted[i] === sorted[i - 1];
      if (same && !used[i - 1]) continue;
      used[i] = true;
      current.push(sorted[i]);
      backtrack();
      current.pop();
      used[i] = false;
    }
  }
  backtrack();
  return result;
}

function combinations(items, k) {
  const result = [];
  const current = [];
  function backtrack(start) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }
    for (let i = start; i < items.length; i++) {
      current.push(items[i]);
      backtrack(i + 1);
      current.pop();
    }
  }
  backtrack(0);
  return result;
}

test("ikki osh, bir choy — 3 ta tartib", () => {
  const routes = uniquePermutations(["osh", "osh", "choy"]);
  assert.deepEqual(routes.map((r) => r.join("-")), [
    "choy-osh-osh", "osh-choy-osh", "osh-osh-choy",
  ]);
});

test("4 ta turli element — 24 ta, hammasi turlicha", () => {
  const all = uniquePermutations(["a", "b", "c", "d"]);
  assert.equal(all.length, 24);
  assert.equal(new Set(all.map((r) => r.join())).size, 24);
});

test("bo'sh ro'yxat — bitta bo'sh tartib", () => {
  assert.deepEqual(uniquePermutations([]), [[]]);
});

test("C(6, 3) = 20", () => {
  assert.equal(combinations([1, 2, 3, 4, 5, 6], 3).length, 20);
  assert.deepEqual(combinations([1, 2], 3), []);
});

✔ ikki osh, bir choy — 3 ta tartib (1.3241ms)
✔ 4 ta turli element — 24 ta, hammasi turlicha (0.2135ms)
✔ bo'sh ro'yxat — bitta bo'sh tartib (0.1073ms)
✔ C(6, 3) = 20 (0.8447ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 81.4696

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga uchta qator qo'shing: qism-to'plamlar, permutatsiyalar, kombinatsiyalar. "Amaliy chegara" ustuniga o'lchovdan n ni yozing (taxminan 1 soniyagacha).

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Kombo variantlari | backtracking, start | O(n · 2ⁿ) | O(n) + natija |
| Kuryer tartiblari | backtracking, used | O(n · n!) | O(n) + natija |
| Banket salatlari | backtracking, k ta | O(k · C(n, k)) | O(k) + natija |

git add 14/MURAKKABLIK.md 14/24-backtracking
git commit -m "14/24: backtracking — qism-to'plam, permutatsiya, kombinatsiya"

12. Real ishda

• Test ma'lumotlari. Funksiyani hamma variantlarda sinash: kirish parametrlarining barcha kombinatsiyalari (masalan, "tema × til × ekran o'lchami"). Bunday testlar ko'pincha qism-to'plam yoki kombinatsiya generatori bilan yasaladi.
• Konfiguratsiya va filtrlar. Mahsulot variantlari (rang × o'lcham), tugmalar kombinatsiyasi, ruxsatlar to'plami — hammasi kombinatorika. Variantlar soni oldindan hisoblanadi, toki interfeys "portlab" ketmasin.
• Optimallashtirish masalalarining boshlanishi. Jadval tuzish, yetkazish yo'li, guruhlarga bo'lish — ko'pincha avval backtracking bilan sinaladi, keyin kesish, dinamik dasturlash yoki ochko'z usul bilan tezlashtiriladi.
• Intervyu. LeetCode'dagi "78. Subsets", "46. Permutations", "77. Combinations" va ularning takrorli variantlari (90, 47) — eng ko'p so'raladigan backtracking masalalari (leetcode.com/problems/subsets). Ularning hammasi shu bitta qolipdan chiqadi.

Xulosa

• Backtracking: tanla → chuqurga tush → bekor qil. Bitta current massivi hamma shoxga xizmat qiladi, shuning uchun bekor qilish shart.
• Holat daraxti tanlovlardan yasaladi; backtracking uni chuqurlik bo'yicha aylanadi.
• Qism-to'plam: start, har tugun — javob, 2ⁿ ta. Permutatsiya: used, faqat barglar — javob, n! ta. Kombinatsiya: start + uzunlik k, C(n, k) ta.
• Natijaga nusxa yozing ([...current]); takroriy elementlarda — saralash va bir qavatda takrorni o'tkazib yuborish.
• O'lchov: 2ⁿ — har element bilan ×2; n! — ×(n + 1); 11 ta permutatsiya ≈ 2,7 s. Backtracking — kichik n uchun.

Keyingi dars: Backtracking chuqur va kesish — N-Queens, Sudoku, jadvalda so'z qidirish va combination sum: keraksiz shoxlarni erta kesib, eksponensial qidiruvni amalda tezlashtirish.

Manbalar

• Steven S. Skiena, "The Algorithm Design Manual", 3-nashr, Springer, 2020 — "Combinatorial Search" bobi (backtracking).
• Donald E. Knuth, "The Art of Computer Programming", 4A-jild, Addison-Wesley, 2011 — kombinatsiyalar va permutatsiyalarni yasash.
• LeetCode: 78. Subsets, 46. Permutations, 77. Combinations — leetcode.com