To be or not to be? That is the Backtracking

Backtracking is often introduced alongside the concepts of permutations and combinations. If you're familiar with Python's itertools, you might be wondering, "Why not just use those?" Well, fear not — backtracking has its own advantages. As the name suggests, think of backtracking like having regrets in life — if only you could go back and make a better choice! That’s exactly what this algorithm does: it explores one choice, checks if it leads to a valid solution, and if not, it backtracks and tries a different path. It’s a step beyond brute-force permutations because it allows pruning of unpromising paths early.

The classic backtracking template involves maintaining an output (your current path of choices) and a position on a timeline (the index you're exploring). At each step, you make a decision — either to include an element or not — much like traversing a binary tree of "yes" and "no" decisions. Indeed "To be or not to be?" This continues until you've reached the end of the array or fulfilled the problem's condition.

<photo credit: https://www.ebay.com/itm/184357972390>

So here’s how it goes: at each step, you make a choice — either add the current element to your path and see if it leads somewhere meaningful, or skip it and explore the other possibility. By the end, you’ll have explored all potential paths or subsets that satisfy the condition.

Below is a cool LeetCode problem that uses backtracking to check whether a given input string can be broken down into palindromic substrings. Hope it helps!

https://leetcode.com/problems/palindrome-partitioning/description/

class Solution:

    def partition(self, s: str) -> List[List[str]]:

        output = []

       

        def is_palindrome(sub):

            return sub == sub[::-1]

        def backtrack(i, current):

            if i==len(s):

                output.append(current[:])

                return

           

            for j in range(i+1, len(s)+1):

                data = s[i:j]

                if is_palindrome(data):

                    current.append(data) #to be

                    backtrack(j, current)

                    current.pop() #not to be

               

        backtrack(0, [])

        return output