## Recursion - Also called Divide n conquer. - Better to say reduce and conquer. - Assume that smaller problem will work and build solution for larger problem. - Solution starts aggregating at base case. ## Backtracking - A) Element of choice - B) Explore all possibilities (Solving question in tree like fashion ) **Steps for Coding:** - Take a decision (When you take a decision, you know that now your problem has been reduced ) - Recur (Solving reduced problem ) - Undo Decision I **Q1 Gray Code** The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. **Q2- Word Break** Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. ``` Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ] ``` _Recursion_ ```java public List wordBreak(String s, Set wordDict) { return word_Break(s, wordDict, 0); } public List word_Break(String s, Set wordDict, int start) { LinkedList res = new LinkedList<>(); if (start == s.length()) { res.add(""); } for (int end = start + 1; end <= s.length(); end++) { if (wordDict.contains(s.substring(start, end))) { List list = word_Break(s, wordDict, end); for (String l : list) { res.add(s.substring(start, end) + (l.equals("") ? "" : " ") + l); } } } return res; } ``` _Recursion with memoization__ ```java public List wordBreak(String s, List wordDict) { return word_break(s, wordDict, 0); } HashMap> map = new HashMap<>(); public List word_break(String s, ListwordDict, int start){ if(map.containsKey(start)){ return map.get(start); } LinkedList res = new LinkedList<>(); if(start == s.length()){ res.add(""); } for(int end = start + 1; end <= s.length(); end++){ if(wordDict.contains(s.substring(start, end))){ List list = word_break(s, wordDict, end); for(String l: list){ res.add(s.substring(start, end) + (l.equals("") ? "" : " ") + l); } } } System.out.println(start); System.out.println(res); map.put(start, res); return res; } ``` **Q3- Generate Paranthesis** Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: ``` [ "((()))", "(()())", "(())()", "()(())", "()()()" ] ``` ```java public List generateParenthesis(int n) { List ans = new ArrayList<>(); backtrack(ans, "", 0, 0, n); return ans; } public void backtrack(List ans, String curr, int open, int close, int max){ if(curr.length() == max * 2){ ans.add(curr); return; } if(open < max){ backtrack(ans, curr + "(", open + 1, close, max); } if(close < open){ backtrack(ans, curr + ")", open, close + 1, max); } } ``` Time Complexity: **Q4- Palindrome Partitioning** Given a string s, partition s such that every substring of the partition is a palindrome. Print all palindromic partitions. Partitioning means that dividing the string into k parts such that: 1. Maintain order 2. Mutually exlusive partitions - no overlap of elements 3. Mutually exhaustive partitions - union of all subsets gets the entire string. 4. Every partition should be a palindrome ``` Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ] Invalid: ["a", "ab"] ``` - Why a backtracking problem? Because you want to find all possible partitions. - Element of Choice? Do I introduce a partition after ith element or not? - How to represent a state? f(i) - At each step, you have two choice, whether to introduce partition not introduce partition. - Also at each step, check if the currString till now is palindrome or not. If it is not, we do pruning. ```java public class Solution { List> resultLst; ArrayList currLst; public List> partition(String s) { resultLst = new ArrayList>(); currLst = new ArrayList(); backTrack(s,0); return resultLst; } public void backTrack(String s, int l){ if(currLst.size()>0 //the initial str could be palindrome && l>=s.length()){ List r = (ArrayList) currLst.clone(); resultLst.add(r); } for(int i=l;i children; TrieNode(char ch, bool isTerminal) { this->ch = ch; this->isTerminal = isTerminal; } }; class Solution { public: vector result; void insert(string word, TrieNode *root) { TrieNode* temp = root; for(int i = 0; i < word.size(); i++) { char ch = word[i]; if(temp->children.find(ch) != temp->children.end()) { temp = temp->children[ch]; } else { temp->children[ch] = new TrieNode(ch, false); temp = temp->children[ch]; } } temp->isTerminal = true; return; } void backtrack(vector>& board, TrieNode* root, int i, int j, bool **visited, string str) { if(i < 0 or j < 0 or i >= board.size() or j >= board[0].size()) { return; } if(visited[i][j] == true) return; char ch = board[i][j]; if(root->children.find(ch) == root->children.end()) { return; } else { root = root->children[ch]; } if(root->isTerminal == true) { result.push_back(str+board[i][j]); root->isTerminal = false; } visited[i][j] = true; backtrack(board, root, i+1, j, visited, str+board[i][j]); backtrack(board, root, i-1, j, visited, str+board[i][j]); backtrack(board, root, i, j+1, visited, str+board[i][j]); backtrack(board, root, i, j-1, visited, str+board[i][j]); visited[i][j] = false; return; } vector findWords(vector>& board, vector& words) { TrieNode *root = new TrieNode('\0', false); for(string word: words) { insert(word, root); } bool **visited = new bool*[board.size()]; for(int i = 0; i < board.size(); i++) { visited[i] = new bool[board[0].size()](); } for(int i = 0; i < board.size(); i++) { for(int j = 0; j < board[0].size(); j++) { TrieNode* temp = root; backtrack(board, temp, i, j, visited, ""); } } return result; } }; ```