Тоо бүрийн хувьд "авах уу, авахгүй юу?" гэж шийдээд бүх 2ⁿ дэд олонлогийг backtracking аргаар гаргана.

IntermediateХугацаа: O(2ⁿ · n)Санах ой: O(n)
HackerRank дээр бодох

Эхлээд жижиг бодлого

{1, 2, 3} олонлогийн бүх дэд олонлогийг гаргая. Тоо бүрийн хувьд "авах уу, авахгүй юу?" гэж асууна. Гурван тоо, тус бүрт хоёр сонголт тул 2 × 2 × 2 = 8 дэд олонлог гарна.

Код "авах" замыг эхэлж үздэг тул хэвлэх дараалал: 1 2 3, 1 2, 1 3, 1, 2 3, 2, 3, хоосон мөр.

Энгийн аргаас санаа руу

Гараар бичихэд эхлээд нэг элементтэй, дараа нь хоёр элементтэйг нь бичдэг. Гэхдээ үүнийг кодонд n-ээс хамааран хэдэн давхар loop болохыг урьдчилан мэдэхгүй.

Гол санаа: тоог нэг нэгээр нь шийдэх. solve(i) нь a[i]-г авах эсэхийг шийднэ. Эхлээд авч cur-д нэмээд цааш явна. Буцаж ирээд түүнийг cur-ээс хасаж, авахгүй замаар явна. "Сонгох, цааш явах, буцааж болиулах" гэсэн энэ загварыг backtracking гэдэг.

Нэр томьёо ба тэмдэглэгээ

solve(i)
a[0..i−1]-ийг аль хэдийн шийдсэн. Одоо a[i]-г шийднэ.
cur
Одоогийн замд авсан тоонууд. vector<int>.
backtrack
Буцаж ирээд сүүлийн сонголтоо болиулах: cur.pop_back().
2ⁿ
n элементтэй олонлогийн дэд олонлогийн тоо.
i = 0cur = {}
Call stack
хоосон

{1, 2, 3} олонлогийн бүх дэд олонлогийг олъё. Тоо бүрийн хувьд "авах уу, авахгүй юу?" гэж асууна.

Алхам 1 / 23
Хурд
  • Ажиллаж буй дуудлага
  • Хүлээж буй
  • Бэлэн дэд олонлог
  • Шалгаж дууссан
Слайд 1 / 6

Авах уу, авахгүй юу?

{1, 2, 3} олонлогоос хэдэн янзын бүлэг сонгож болох вэ? Тоо бүрийн хувьд "авах уу, авахгүй юу?" гэж асуугаад бүх замаар явна.

subsets-backtracking.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[20];
vector<int> cur;
void solve(int i) {
if (i == n) {
for (int x : cur) cout << x << ' ';
cout << '\n';
return;
}
cur.push_back(a[i]);
solve(i + 1);
cur.pop_back();
solve(i + 1);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
solve(0);
return 0;
}

Юунд хэрэгтэй вэ?

Олонлогийн бүх дэд олонлогийг гаргана. Сонгох, цааш явах, буцааж болиулах гэсэн backtracking-ийн чухал загварыг сурна.

Яаж ажилладаг вэ?

1. solve(i) нь a[i]-г авах эсэхийг шийднэ. cur нь одоогоор авсан тоонууд. 2. i == n бол бүх тоог шийдсэн байна. cur доторх тоонуудыг хэвлэнэ. 3. a[i]-г cur-д нэмээд solve(i + 1)-ийг дуудна. Энэ бол "авах" зам. 4. Буцаж ирээд a[i]-г cur дотроос гаргана (backtrack). 5. Дахин solve(i + 1)-ийг дуудна. Энэ бол "авахгүй" зам. Оролт: n, дараагийн мөрөнд n тоо. Хоосон олонлог хоосон мөр болж хэвлэгдэнэ.

Яагаад зөв, хэр хурдан бэ?

Дэд олонлог бүр тоо бүрийн хувьд "авсан" эсвэл "аваагүй" гэсэн n шийдвэрээр тодорхойлогдоно. solve эдгээр шийдвэрийн бүх хослолыг яг нэг удаа үздэг тул дэд олонлог бүр яг нэг удаа хэвлэгдэнэ. cur.pop_back() нь cur-ийг дуудлагын өмнөх байдалд нь буцаадаг тул "авахгүй" зам цэвэр эхэлнэ.

2ⁿ дэд олонлог, тус бүрийг хэвлэхэд n хүртэл тоо: хугацаа O(n · 2ⁿ). n = 20 бол 1 сая дэд олонлог, 20 сая орчим үйлдэл. n = 30 бол тэрбум дэд олонлог, хэт удаан.

Түгээмэл алдаа

  • cur.pop_back()-ийг мартах. "Авахгүй" зам дээр авсан тоо cur-д үлдээд хариу буруу болно.
  • Base case-ийг i > n гэж бичих. Сүүлийн тоог шийдсэн мөч нь i == n.
  • n том үед бүх дэд олонлогийг гаргах гэж оролдох. n > 25 бол өөр арга хэрэгтэй.

Хязгаарын тохиолдол

  • n = 1, {5}: 5 ба хоосон мөр хэвлэгдэнэ.
  • Хоосон дэд олонлог үргэлж хамгийн сүүлд хоосон мөр болж гарна.
  • Ижил тоо давтагдвал {1, 1} гэх мэт ижил дэд олонлог хоёр удаа хэвлэгдэнэ.

Өөрийгөө шалга

  1. 4 элементтэй олонлог хэдэн дэд олонлогтой вэ?

    Хариу харах

    16. 2⁴ = 16, хоосон олонлогийг оруулаад.

  2. {1, 2, 3} дээр хэвлэгдэх дөрөв дэх мөр юу вэ?

    Хариу харах

    1. Дараалал нь 1 2 3, 1 2, 1 3, 1.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.{4, 7} дээр solve-ын дуудлагуудыг tree хэлбэрээр зур. Юу хэвлэгдэх вэ?

    Hint харах

    Root нь solve(0), cur = {}. Зүүн тал нь "авах" зам.

    Хариу ба тайлбар

    Навчнууд зүүнээс баруун тийш {4, 7}, {4}, {7}, {}. Хэвлэгдэх нь 4 7, 4, 7, хоосон мөр.

  2. 2.Зөвхөн нийлбэр нь k-тэй тэнцүү дэд олонлогуудыг тоол. {2, 3, 5}, k = 5 бол хэд вэ?

    Hint харах

    cur-ийн оронд одоогийн нийлбэрийг solve-д дамжуул.

    Хариу ба тайлбар

    solve(i, s): i == n үед s == k бол cnt-г нэмнэ. Авах зам solve(i + 1, s + a[i]), авахгүй зам solve(i + 1, s). Хариу 2: {2, 3} ба {5}.

  3. 3.Recursion ашиглахгүйгээр бүх дэд олонлогийг bitmask-аар гарга.

    Hint харах

    0-ээс 2ⁿ − 1 хүртэлх mask бүрийн i дэх bit нь a[i]-г авсан эсэхийг заана.

    Хариу ба тайлбар

    for (int mask = 0; mask < (1 << n); mask++) дотор if (mask >> i & 1) бол a[i]-г хэвлэнэ. Хугацаа O(n · 2ⁿ) хэвээр.

Жишээ

Оролт

3
1 2 3

Гаралт

1 2 3
1 2
1 3
1
2 3
2
3

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.