Generate All Palindromic Decompositions Of A String ("Palindrome Partitioning" on Leetcode)

Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 Intuitive Video Explanations 🏃 Run Code As You Learn 💾 Save Progress ❓New Unseen Questions 🔎 Get All Solutions Question: Given a string, return all decompositions of the string that consist of only palindromes. Example: Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ] Why is this problem backtracking? It is backtracking because we will be expressing all of the possibilities of a search space given constraints. When we need to represent many decisions and possibilities, backtracking is the tool you should pull from your pocket. Approach 1 Generate all decompositions and then only add the palindromic decompositions to our answer. This is highly exponential in time since there are 2^(n - 1) palindromic decompositions. This wastes a lot of time since we will continue to build on a decomposition that immediately disqualifies as palindromic. Approach 2 We will take "snapshots" of snippets as we advance through the string and see if they can add to the decomposition that we want to build. The 3 Keys To Backtracking: Our Choice The start and the end of a "snapshot" that we want to add to a decomposition we are working on. Our Constraints Each piece of the decomposition must be a palindrome, we cannot choose and advance on a non-palindrome snippet. Our Goal Decompose the whole string. When our decomposition progress index is the length of the array then we know that we have achieved this. Complexities Time: O(n * (2^n)) Worst case, but much better than approach 1 since this is a rare worst case where all decompositions turn out to be palindromic (a string of all 1 character). Our best case becomes greatly improved. We are basically taking subsets so (2^n) and the O(n) time to copy array to our answer. Space: O(n) At worst we will always go n stack frames deep in our recursion since an all single character decomposition is a