Recursion & Backtrack

В тази секция ще разгледаме как да решаваме задачи с изчерпване, ползвайки рекурсия и търсене с връщане (backtrack). За някои от задачите ще ви се наложи да измислите оптимизации, за да бъде достатъчно бързо решението ви - например в какъв ред да извиквате под-задачите, кои клони на рекурсията нямат смисъл да бъдат обходени и могат да бъдат "изрязани" (наричано на Английски "pruning"), както и други.

Подходяща тема, която можете да прочетете е Рекурсия и търсене с връщане.

Упражняват се лесни до средно-трудни задачи, в които трябва да се имплементира рекурсивно решение. Задачата Schedule с дадените ограничения може да се реши с бектрек, макар че има доста по-добро (полиномиално) решение, което ще разгледаме в секцията Greedy. Задачата Ruler е относително сложна (нужни са няколко оптимизации, за да върви достатъчно бързо дори само да изчислим отговорите локално), като, за съжаление, отговорите могат много лесно да бъдат намерени в интернет.