Recursion & Backtrack
В тази секция ще разгледаме как да решаваме задачи с изчерпване, ползвайки рекурсия и търсене с връщане (backtrack). За някои от задачите ще ви се наложи да измислите оптимизации, за да бъде достатъчно бързо решението ви - например в какъв ред да извиквате под-задачите, кои клони на рекурсията нямат смисъл да бъдат обходени и могат да бъдат "изрязани" (наричано на Английски "pruning"), както и други.Подходяща тема, която можете да прочетете е Рекурсия и търсене с връщане.
Упражняват се лесни до средно-трудни задачи, в които трябва да се имплементира рекурсивно решение. Задачата Schedule с дадените ограничения може да се реши с бектрек, макар че има доста по-добро (полиномиално) решение, което ще разгледаме в секцията Greedy. Задачата Ruler е относително сложна (нужни са няколко оптимизации, за да върви достатъчно бързо дори само да изчислим отговорите локално), като, за съжаление, отговорите могат много лесно да бъдат намерени в интернет.
Unique
28
|
25
Company
39
|
35
Closest Number
24
|
22
Sudoku
6
|
4
Schedule
14
|
9
Orderings
67
|
37
Product
20
|
12
Ruler
6
|
27
Persistence
15
|
33