backtracking – Tarik Billa

Difference between backtracking and recursion?

September 25, 2023 by Tarik

That question is like asking what’s the difference between a car and a DeLorean. In recursion function calls itself until reaches a base case. In backtracking you use recursion in order to explore all the possibilities until you get the best result for the problem. Can be a bit hard to understand, I attach some … Read more

what is AC means in leetcode, is it algorithm technique like DP?

September 1, 2023 by Tarik

AC stands for ‘Accepted’ solution.

How to calculate time complexity of backtracking algorithm?

June 2, 2023 by Tarik

In short: Hamiltonian cycle : O(N!) in the worst case WordBreak and StringSegment : O(2^N) NQueens : O(N!) Note: For WordBreak there is an O(N^2) dynamic programming solution. More details: In Hamiltonian cycle, in each recursive call one of the remaining vertices is selected in the worst case. In each recursive call the branch factor … Read more