Backtracking 

Start at 2018.07.03
End   at 


Base Knowledge:
 
回溯算法的定义：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。适用于求解组合数较大的问题。
对于回溯问题，总结出一个递归函数模板，包括以下三点
  • 递归函数的开头写好跳出条件，满足条件才将当前结果加入总结果中
  • 已经拿过的数不再拿 if(s.contains(num)){continue;}
  • 遍历过当前节点后，为了回溯到上一步，要去掉已经加入到结果list中的当前节点。
针对不同的题目采用不同的跳出条件或判断条件。
下面通过几个例子来说明对上述模板的使用

https://www.codetd.com/article/1054326 


 

77 
 套用模板
  1. 退出条件： out.size（） ==  k
  2. 已经拿过的数处理： pos = pos + 1 when recursion
  3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion
  backtracking(n, k, pos + 1, out, res);

 
 39 Combination Sum  (similar 77)
 
 套用模板
 1. 退出条件： target cut down to zero
 2. 已经拿过的数处理：  allow use the same number multiple times，pos = pos
 3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion
 
 backtracking(candidates, target - candidates[pos], pos, out, res);
 
40 Combination Sum II (similar to 39)
  套用模板
  1. 退出条件： target cut down to zero 
  2. 已经拿过的数处理：  do not allow use the same number multiple times，pos = pos + 1
  3.  回溯：out.push_back(i) before recursion, and out.pop_back() after recursion
  backtracking(candidates, target - candidates[pos], pos + 1, out, res);
  Duplication process:
  if (pos > start && candidates[pos] == candidates[pos - 1])
                continue;  // next loop
 
216 Combination Sum III (similar to 40)
 套用模板 
 1. 退出条件： n cut down to zero and k cut down to zero as well
 2. 已经拿过的数处理：  do not allow use the same number multiple times，pos = pos + 1 
 3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion 
    backtracking(n - pos, k - 1, pos + 1, out, res); 
    No duplication could be generated.
 
 
46
Permutations    

(similar to 39)





 套用模板
 1. 退出条件： out.size() == nums.size() 
 2. 已经拿过的数处理：  do not allow use the same number multiple times，
                     but need start from pos 0 each time, and skip visited number.
  
 3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion,
         visited[pos] = true before recursion, and visited[pos] = false after.
  
 backtrack(nums, visited, out, res);
 
 47 Permutations II   
 Same with 46, but use the following two lines to get rid of duplication,
 please note you cannot use unordered_set here, It cannot be initialized with an array.


  set<vector<int> > hashSet(res.begin(), res.end());
  res = move(vector<vector<int> >(hashSet.begin(), hashSet.end())); 


 


60 Permutation Sequence (similar to 39)


 套用模板


 1. 退出条件： out.size() == n  


 2. 已经拿过的数处理：  do not allow use the same number multiple times，


                      but need start from pos 0 each time, and skip visited number.


 3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion, 


         visited[pos] = true before recursion, and visited[pos] = false after. 


 


 


 Early exit: if (count >= k) return; // no need for more computation
 backtracking(n, k, count, visited, out, res); 


 


78 Subsets


 

 套用模板 


 1. 退出条件： out.size() == nums.size() 


 2. 已经拿过的数处理：  do not allow use the same number multiple times，pos = pos + 1


 3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion, 


 visited[pos] = true before recursion, and visited[pos] = false after.   


 


 backtracking(nums, pos + 1, out, res); 


 通常退出条件和存储条件 （加入res的条件）一样，但本题不一样，无条件保存中间结果，因为都是子集合。 如果只是求排列组合，


 则 out.size() == nums.size()  才加入res array


 


90 Subsets II    (similar to 78)


Same idea, except this problem input could contain duplicate numbers. So we have to


use a hash set (ordered set, not unordered_set) to collect all the subset to get rid of


duplicated subset. Also we need to sort the input number array before going into backtracking


 



 


17 Letter Combinations of a Phone Number (Similar to 39, 78)

 套用模板 

 1. 退出条件： out.size() == digits.size()  

 2. 已经拿过的数处理：  do not allow use the same char multiple times，pos = pos + 1 

 3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion,     backtracking(digits, pos + 1, out, res); 



One thing to note here is that we need do the backtracking function and push pos before it inside the nested double for loop (outer for digits, inner for chars corresponding to that digits, save this mapping in a hash map for easier access)


 


 


22 Generate Parentheses 



 套用模板 

 1. 退出条件： out.size() == n * 2  


 2. 已经拿过的数处理： do not allow use the same char multiple times，left = left + 1,

                right = right +  1, but guard the backtracking function with two 

                conditions: left < n for left recursion,  right < left for right

                recursion 

 3. 回溯： no backtracking actually, (so this is just dfs) 



  if (left < n)
            backtracking(n, left + 1, right, out + "(", res);
  if (right < left)
            backtracking(n, left, right + 1, out + ")", res); 



357 Count Numbers with Unique Digits


 套用模板


 1. 退出条件： pre >= maxVal  


 2. 已经拿过的数处理：do not allow use the same number multiple times，


                  but need start from pos 0 each time, and skip visited number.


                  except the first time, start from 1 (to avoid dealing with leading 0) 


 3. 回溯：visited[pos] = true before recursion, and visited[pos] = false after. 


 


 count += backtracking(pre * 10 + pos, maxVal, visited);





 


784 Letter Case Permutation  


 


Backtrack DFS


 


Time complexity O(N*2^I) I: # of letters


Space complexity O(n) + O(N*2^I) stack + sols?


 


def dfs(S, i)


  if i == len(S)


     ans.append(S)


     return


  dfs(S, i + 1)


  if S[i] is letter :


      toggle S[i] # S[i] ^= (1 << 5)


      dfs(S, i + 1)


      toggle back S[i]  # S[i] ^= (1 << 5)


 


ref:  http://zxi.mytechroad.com/blog/searching/leetcode-784-letter-case-permutation/


 


 


 


 

667 Beautiful Arrangement II   (not suitable for backtracking)





if you have n number, the maximum k can be n - 1;

if n is 9, max k is 8.

This can be done by picking numbers interleavingly from head and tail,

// start from i = 1, j = n;
// i++, j--, i++, j--, i++, j--

1   2   3   4   5
  9   8   7   6
out: 1 9 2 8 3 7 6 4 5
dif:  8 7 6 5 4 3 2 1




Above is a case where k is exactly n - 1

When k is less than that, simply lay out the rest (i, j) in incremental

order(all diff is 1). Say if k is 5:

     i++ j-- i++ j--  i++ i++ i++ ...
out: 1   9   2   8    3   4   5   6   7
dif:   8   7   6   5    1   1   1   1






306 Additive Number 


A simpler version of 842, only difference is must use long long to save all the 


Fibonacci numbers.


 


 


401Binary Watch  




Similar to 77 Combinations. We could generate the time user a dfs helper function.


If we want to get the time with num LED lights, we could use i for hour and use 


num - i LED for minutes. If both are valid time we add it to the result.




For hours. If we want to use i LED numbers, we could use any i number from 


 {1,  2, 4, 8}, which we could do in the following format:




   for (int i = pos; i < nums.size(); i++)
       dfsHelper(nums, cnt - 1, i + 1, out + nums[i], res);


 


  exit, once cnt reaches zero. Similarly for minutes. 


 


 


 


Second Time


 =============================================================


 


89 Gray Code     


 


  套用模板


  1. 退出条件： n == 0, { res.push_back(out.to_ulong()); return; } 


  2. 已经拿过的数处理： n = n - 1;


  3. 回溯： 


          backtracking(n - 1, out, res);
          out.flip(n - 1);
          backtracking(n - 1, out, res);


 


 


131 Palindrome Partitioning    


 

 套用模板 

 1. 退出条件： out.size() >= start

 2. 已经拿过的数处理：  do not allow use the same char multiple times，pos = pos + 1,

                     guarded with isPalindrome() condition nested in the loop from

                     pos = start to pos = s.size() - 1. 

  3. 回溯： out.push_back(s.substr(start, pos - start + 1)) before recursion, and out.pop_back() after recursion,



 


backtracking(s, pos + 1, out, res); 


 


 


 





842





 

 套用模板 

 1. 退出条件： if (start >= n && res.size() >= 3), i.e: If we reached end of

            string and we have at least 3 elements in our sequence then return true

 2. 已经拿过的数处理：  do not allow use the same char multiple times，

                     start = start + i, where i is the length of the first 

                     split part. guarded with isFibonacci()or they are numbers

                     from the first two split parts.

                     pos = start to pos = s.size() - 1. 

  3. 回溯： res.push_back(num) before recursion, and res.pop_back() after recursion.

  if (backtracking(S, start + i, res))
      return true;

  Note here the problem only ask return any split, we don't have to save all the results, therefore out and res are combined together.


 


 








93





 

 套用模板 

 1. 退出条件： if (k == 0), if the remaining s is empty(), we push_back out into res, otherwise,we don't push_back, we always return when k == 0 no matter push or not.

 2. 已经拿过的数处理：  do not allow use the same char multiple times，

                     next start from s.substr(len)

  3. 回溯： no backtracking, always try 3 different length len = 1; len <= 3; len++.

   backtracking(s.substr(len), k - 1, out + str + (k > 1 ? "." : ""), res);







79 Word Search   

 套用模板 

 1.
 退出条件： if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[start] != board[i][j] return false;

if (word.size() - 1 == start)

return true;



 2. 已经拿过的数处理：  do not allow use the same char multiple times，

                     start = start + 1;

  3. 回溯： save and set board[i][j] to '#' before backtracking recursion.

            bool res = backtracking(board, word, i - 1, j, start + 1) || 

                backtracking(board, word, i + 1, j, start + 1) || 

                backtracking(board, word, i, j - 1, start + 1) ||

                backtracking(board, word, i, j + 1, start + 1);

        restore it after:  board[i][j] = curChar;





211 Add and Search Word - Data structure design

Use trie to (or dictionary tree, prefix tree) as the basic data structure.

ref: 208 Implement Trie (Prefix Tree)    



 套用模板 

 1.
 退出条件：if (start == word.size())

            return p->isWord;

   



 2. 已经拿过的数处理：  do not allow use the same char multiple times，

                     start = start + 1;







3. 回溯：         

   if (word[start] == '.') {

            for (const auto& c : p->child) {

                if (c && search(word, c, start + 1))

                    return true;

            }

            return false;

        }



  

        auto idx = word[start] - 'a';

        return p->child[idx] && search(word, p->child[idx], start + 1);








































Comments











Post a Comment























Popular posts from this blog









zhitongguigu





















Lecture 1:   To do: (117? 199)  Using Morris Traversal,  we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In  this traversal, we first create links to Inorder successor and print  the data using these links, and finally revert the changes to restore  original tree.    numerical_limits<int>::min()   <==> INT_MIN   








Read more










Array Part2





















 Two pointers    977  Squares of a Sorted Array          We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction.   Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique.     11  Container With Most Water            O(N) time and O(1) space, since better candidadates must use the taller line of l and r   therefore we can use two pointer keep moving towards each other until they meet. Always   abandon the shorter line while moving.        80  Remove Duplicates from Sorted Array II           tail = 0;   for (int i = 0;  i < nums.size(); i++)              if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                   nums[tail++] = nums...








Read more










Two pointers (Part 1)





















     344  Reverse String           Use two pointers i, j. keep switching elements at position i, j while i < j.         string reverseString(string s) {          for (int i = 0, j = s.size() - 1; i < j; i++, j--)              swap(s[i], s[j]);                      return s;       }     345  Reverse Vowels of a String          Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not.             283  Move Zeroes          Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero.          349  Intersection of Two Arrays        ...








Read more