Leetcode Pattern 3 | Backtracking

Here is the article.

Algorithms:

Leetcode 78. Subsets
90. Subsets II
39. Combination sum
40. Combination Sum II
51. N-Queens

My practice

78. Subsets - submission in May 2019
90. Subsets II - no submission
39. Combination sum - a year ago, two year ago
40. Combination sum II - a year ago, two year ago

78
Here is my post on leetcode discuss I wrote on June 22, 2019.

39
I wrote a post to share on June 22, 2019 based on practice in 2018. Here is the link.
I wrote a post to share on June 22, 2019 based on practice in 2017. Here is the link.

40.
Here is my discussion link for practice in 2018.
Here is my discussion link for practice in 2017.

51
Here is my post written on June 22, 2019. The code was submitted on January 26, 2016. I missed 2016. I got my first Amazon onsite in the city of Vancouver, Canada. I turned 50 years old in October, 2016.

90 
Here is my practice, first one in 2019. The code should be simplified. There are some duplicated code. 

Here is C# practice using recursive solution, I studied the code written by an Amazon engineer. 

HackerRank: string algorithm - Reverse Shuffle Merge - Stack, backtracking techniques

May 26, 2016

Reverse Shuffle Merge - Problem statement:

https://www.hackerrank.com/challenges/reverse-shuffle-merge

Algorithm analysis:

Use test case: "abcacb" to explain the solution: 

int[] add = new int[26], 

int[] skip = new int[26]

a - 0, b - 1, c -2 

add[0] = 1, add[1] = 1, add[2] = 1, 

skip[0] = 1, skip[1] = 1, skip[1] =1, 

Find smallest lexical string. 

reverse input char one by one:

push b into stack, 

'c' > ''b', then, push c into stack

stack:

c

b

Now, a is scanned, 'a' < stack.peek() = 'c', skip[2] = 1 > 0, 

backtracking, pop c out of stack, skip[2] = 0

Now, 'a' < stack.peek() = 'b', skip[1] = 1 > 0, 

backtracking, pop b out of stack, then adjust skip[1] = 0

add[0] >  0, push a into stack, add[0] = 0, 

next, c is scanned, cannot skip, push into stack, 

next, b is scanned, cannot skip, push into stack, 

next, a is scanned, skip a. 

stack.ToArray(), keep stack iterator order, "bca", 

Array.Reverse(stack.ToArray()) -> "acb"

Lexical smallest string. 

previous blog: 

http://juliachencoding.blogspot.ca/2016/04/april-3-2016-httpsgist.html

warmup practice:

https://gist.github.com/jianminchen/f3c4b8249b8233771183f1a7f5d01c12

Second practice:

https://gist.github.com/jianminchen/c695be78345751a5f389ba3332c33342

so many bugs in second practice:

1. confused on skip, add array --, ++; line 71, line 80 did the opposite.

2. string reverse, char[], string, Array.Reverse etc. lookup

3. add one more test case: "abcacb",

    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.

4. while statement from line 64 - 67, fix compile error.

   both are ok to compile:

(char)stack.Peek() > runner)

(char)stack.Peek() - runner > 0)

Third practice:
The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb", 
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

https://gist.github.com/jianminchen/8e2c28262dd3d13c4db856feaed5603e

Fourth practice:

1. create a new function getIndex - on line 100 - 103
2. after reading through the code, still missed a bug in writing - on line 55; debug the code and find
the result of first test case "abcacb" should be "acb", but it was "bca".

Julia examined line by line, but still missed the bug on line 55.

https://gist.github.com/jianminchen/7572e92ea48211d3d05c557d97601dbf

Read C# string constructor char[]: spend 10 - 20 minutes to read all constructors of string in C#.
https://msdn.microsoft.com/en-us/library/aa331865(v=vs.71).aspx

Binary Tree Preorder Traversal - Iterative Solution - Warm up Practice

May 25, 2016

Review blogs - Leetcode binary tree preorder traversal

C# practice:

use stack, and also know the order to push child nodes: right child first, and then left child next.

Code is here.

Question and Answer:
1. How is the practice?

Julia first thought about using queue to implement the solution, left child first, and then right child next. But, it does not work, since left child's left child should go to traversal first before right child. So, she had to stop.

Then, she tried to look into iterative solutions in general through Google, and also checked her previous practice.

Next time, go through a test case, do some analysis on the test case. Draw some diagram, help yourself to analyze, at least behaves like a teacher.

2. Things to work on through the practice?
queue -> stack -> opposite order to push into stack

3. Can you describe the process using your own words, a few of drawings to help the thinking process?

First, read the wiki article about stack.

Let us work on a simple test case:

The preorder traversal of tree: 1 2 3 4 5 6 7
When the root node 1 is visited, 2 and 5 should be added to some data structure, 3 and 4 will be added after 5, but output of 3 and 4 should be before 5.
In other words, the data structure should accommodate last in first out feature. So, it is stack!
Once stack is chosen to use, then work out the simple tree first with 3 nodes:

preorder traversal: 1 2 5
so, push 1 into stack, and then, pop out. 5 is pushed in stack first, and then it is turn of 2.

Next, work on the test case: tree - preorder traversal 1 2 3 4 5 6 7
1 is pushed into stack,
1 is on the top of stack, 1 is popped out,

1's right child 5 is pushed into stack,
1's left  child 2 is pushed into stack,

2 is popped out from stack,

2's  right child 4 is pushed into stack,
2's  left  child 3 is pushed into stack,

3 is popped out from stack,
4 is popped out from stack,

5 is popped out from stack,

5's right child 7 is pushed into stack,
5's left  child 6 is pushed into stack.

6 is popped out from stack,
7 is popped out from stack.

3. Most favorite problem solving using stack?

HackerRank: string algorithm - Reverse Shuffle Merge (IV)

warmup practice - C# practice code

Second practice:

C# code

so many bugs in second practice:
1. confused on skip, add array --, ++; line 71, line 80 did the opposite.
2. string reverse, char[], string, Array.Reverse etc. lookup
3. add one more test case: "abcacb",
    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.
4. while statement from line 64 - 67, fix compile error.
   both are ok to compile:

(char)stack.Peek() > runner)
(char)stack.Peek() - runner > 0)

Third practice:

The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb",
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

C# practice

August 8, 2016

Work on facebook code lab, preorder iterative solution. Chicken out! Forget to enforce the rule, right child goes to stack first, and then, left child goes to stack afterwards. And then, instead, nervousness kicked in, gave up in 5 minutes, looked up blogs.

Need more practice!

3 smart choices to ask myself: 

stack vs queue ->
left, right who goes first ->
enforce rule, null pointer will not go into stack, save time ->

one node ->
3 node tree - complete binary tree ->
7 node tree - complete binary tree

Back tracking - N Queen problem

April 24, 2016

Review N Queen problem, this one makes me easy to follow:

http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

My own blog:

http://juliachencoding.blogspot.ca/search/label/N-Queens%20problem

Find one problem on HackerRank:

https://www.hackerrank.com/challenges/queens-on-board

Leetcode 17: Letter Combinations of a phone number (DFS)

January 24, 2016
 
17 Letter Combinations of a phone number (DFS)

Julia likes to focus on basic things about algorithms, she tries to focus on recursive function design, BFS, DFS, backtracking. Here is her favorite DFS algorithm, she tries to build more fun memory about DFS algorithm, every time she works on DFS algorithm, she is so happy and eager to share her 2 cents, learned from Leetcode blogs - all her favorite blogs.

http://www.cnblogs.com/grandyang/p/4452220.html
Analysis from the above blog:
这道题让我们求电话号码的字母组合，即数字2到9中每个数字可以代表若干个字母，然后给一串数字，求出所有可能的组合，相类似的题目有 Path Sum II 二叉树路径之和之二，Subsets II 子集合之二，Permutations 全排列，Permutations II 全排列之二，Combinations 组合项， Combination Sum 组合之和和 Combination Sum II 组合之和之二等等。我们用递归Recursion来解，我们需要建立一个字典，用来保存每个数字所代表的字符串，然后我们还需要一个变量level，记录当前生成的字符串的字符个数，实现套路和上述那些题十分类似，

Her practice is too weak in 2015.
https://github.com/jianminchen/Leetcode_C-/blob/master/LetterCombinationOfAPhoneNumber.cs

Missing in the last practice:
1. Use iterative solution, but lack of analysis - (comment area, hard to review)
2. Should focus on DFS solution, basic things.

New practice in January 2016:
1. using recursive to solve the problem, it is fast and quick way to solve it in 10 minutes.
2. Only need to write a few lines of code.
3. Need to design recursive function.
4. Need to do backtracking,
5, Need to do char, string, int a few types, and also do type conversion.

Julia's practice, it took her 27 minutes to write down, compile, and have some comment written.
https://github.com/jianminchen/Leetcode_C-/blob/master/17LetterCombinationOfAPhoneNUmber_DFS.cs

January 24, Read more blogs on this question:

和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母，并加入当前combination中传到下一层递归。
Iterative solution: 这里需要克隆多份之前的解集。
http://bangbingsyb.blogspot.ca/2014/11/leetcode-letter-combinations-of-phone.html

Java, using hashmap - Good idea
http://blog.welkinlan.com/2015/10/25/letter-combinations-of-a-phone-number-leetcode-java/

终于出现我最不擅长的递归题了，这道题是经典递归题，标准DFS解法，应作为模板牢牢记住。
http://simpleandstupid.com/2014/10/16/letter-combinations-of-a-phone-number-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/

So, Julia is not good at recursive function design as well. So, she likes to search a blog and find the most important tip she can grasp in next 20 minutes.

Array initiliazation can be in one line instead of more than 8 lines
http://yucoding.blogspot.ca/2013/01/leetcode-question-42-letter.html

DFS, backtracking is clear in the code.
http://rleetcode.blogspot.ca/2014/02/letter-combinations-of-phone-number-java.html

Java code, member of class - hashmap - static - first time read static - declare variables sharing static in statement. (missing backtracking? or does not matter)
https://github.com/rffffffff007/leetcode/blob/master/Letter%20Combinations%20of%20a%20Phone%20Number.java

very well written,
http://codesniper.blogspot.ca/2015/01/17-letter-combinations-of-phone-number.html

using vector instead of hashmap
http://yumei165.blogspot.ca/2013/04/letter-combinations-of-phone-number-c.html

Good analysis - read the analysis in the following blog -

• 这个是一个结果是排列组合的问题,一个类似的问题就是小组赛N个队, 相互之间的比赛 列表. 这种问题就是回溯法
• 回溯法最重要的就是要"先加再减" (Julia's comment -> backtracking ) 
• 回溯法函数参数的设计是把结果当成参数(此处是用参数引用), 返回值返回一个void. 这样容易设计递归.
• java的做法会比c++看起来麻烦一点, 而且java是无法做到真的const String数组

http://harrifeng.github.io/algo/leetcode/letter-combinations-of-a-phone-number.html

九章算法
http://www.jiuzhang.com//solutions/letter-combinations-of-a-phone-number/

Analysis from the following blog:
Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 
http://buttercola.blogspot.ca/2014/09/leetcode-letter-combinations-of-phone.html

use this one as my example to write a good solution. Good style!
https://segmentfault.com/a/1190000003766442

Excellent code style.
http://shanjiaxin.blogspot.ca/2014/02/letter-combinations-of-phone-number.html

So, put together something for DFS /backtracking algorithm - favorite tips:
1. DFS, do not forget backtracking, using Chinese words, "先加再减". 
2. Recursive function design:
    Return result C#: IList<string>, 
    put it as input argument or member variable of class Solution 
3. Remember a tip to convert a char to int, very basic convert using this: 
    Char c (no one can remember the ascii value of '0', but use type conversion c-'0', char to int; in other words, compare to relative char, get the value by type conversion automatically).
    c - '0' 

4. dictionary declaration, common and easy way is to declare one dimension array:

    String[] table = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

5. using C# or Java, string class is not good, using StringBuilder class instead. 

6. Remember one or two DFS algorithms, use them to relax and help to figure out design issue, difficulty level of DFS problem solving - honestly, it is easy and quick solution, less time-consuming compared to an iterative solution, more time-consuming DP with memorization solution. 
   

Leetcode 51: N - Queen problems

January 12, 2016

Encourage myself to write blogs about leetcode questions. The following talk encourages me a lot. 

https://www.youtube.com/watch?v=R22dJ7bn-pU&list=PLgYNPs-V9YFPqcnEvbIy5hFE40BjxMbjw&index=2
Hiring Rockstars by Roger Philby

the person likes to write, and then the person must love to read, and then the person must be very curious and intellectual. 

So, Julia likes to build up a good habit to write, and then, to read, and to be curious, and to be intellectual. 

Julia is working on recursive function design, how to handle N-Queen problems. After 6 months, she totally forgets how to solve the problem; So, she continues to read more blogs about this algorithm. 

Review the algorithm again. The following blog gives a good explanation, help me understand the algorithm better.
 blog1 (Java programming language): 
http://blog.csdn.net/linhuanmars/article/details/20667175

Amazed that a person can work on algorithms problems and finish over 300 questions/year, people love algorithms and they must know the power of algorithms to save time and improve efficiency at work. 

http://buttercola.blogspot.ca/search/label/Leetcode
http://buttercola.blogspot.ca/2014/09/leetcode-n-queens.html
Leetcode 314:
https://github.com/jianminchen/Leetcode_C-/blob/master/BinaryTreeVerticalOrderTraversal_314.java

Julia likes to work on the analysis of the algorithm, this pseudo code in the blog may help her quickly recover, from nervous to get familiar with the algorithm. 

• • 
    
  http://yucoding.blogspot.ca/2013/01/leetcode-question-59-n-queens.html

The following blog is well-written, and Julia should write a similar solution using C#, to express her appreciation of good variables names, good analysis. (Rating: 10 from 1-10) 

https://polythinking.wordpress.com/2013/02/27/leetcoden-queens-i-and-ii/

It is fun to read solutions in C++/Java.

Write another version of N-Queen problem in C# to entertain. 
https://github.com/jianminchen/Leetcode_C-/blob/master/51NQueenProblem_B.cs

Good advice from the blog 1: 基本上大部分NP问题的求解都是用这个方式，比如Sudoku Solver，Combination Sum，Combinations，Permutations，Word Break II，Palindrome Partitioning等，所以只要把这个套路掌握熟练,多练习. 

Feb. 2, 2016 It is also a DFS algorithm. 

Backtracking algorithm: rat in maze

Sept. 10, 2015

  Study again the back tracking algorithm using recursive solution, rat in maze, a classical problem. Made a few of mistakes through the practice, one is how to use two dimension array, another one is that "not all return path returns value", not so confident that "return false" at the end of function.

  重温二年前做过的算法题, Rat in Maze, 为自己惭愧! 二年前的练习, 没有任何的参考网页信息, 也没有算法讨论, 尝试改进. 感觉到自己的差距, 这次练习, 着重强调把算法能背出来. 一步一步写出来, 发现几个错误. 二维数组不熟悉, 耽误了十几分钟; 另外, 就是, "return false" 在递归函数最后一句, 先是忘了. 总之, 这个经典题目, 十分钟写不出来; 需要二个数组, 边界条件检测, 一点印象没有.

  Here are my favorite blogs about this problem:

1. http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

2. http://algorithms.tutorialhorizon.com/backtracking-rat-in-a-maze-puzzle/

3. https://www.cs.bu.edu/teaching/alg/maze/


  Julia's C# pratice:

  https://github.com/jianminchen/AlgorithmsPractice/blob/master/RatInAMaze_BackTracking.cs

  And then, try to find more discussion about this problem, came cross blogs to challenge my analysis skills. 搜一下Google, 找到一个很有深度的网页, 看了以后, 体验一下代码, 感觉比自己的水平高了几个档次.

  http://blogs.msdn.com/b/mattwar/archive/2005/02/03/366498.aspx

  http://blogs.msdn.com/b/mattwar/archive/2005/02/11/371274.aspx

  More code to read and then play:

http://www.evercrest.com/ext/CheeseAppropriator.cs

  and C# practice:

https://github.com/jianminchen/AlgorithmsPractice/blob/master/MousingAround.cs

January 10, 2016
Review the algorithm

Follow up 

April 27, 2017

Leetcode 37: Sudoku Solver

July 19, 2015

Problem statement:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

Solution 1: 

Great blog to read:

http://blog.csdn.net/fightforyourdream/article/details/16916985

And then, start to implement the solution using C# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program.cs

Solution 2: 

Read the blog,
http://blog.csdn.net/linhuanmars/article/details/20748761

and then, implement the solution using c# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program2.cs

Solution 3: (good workout on C# KeyValuePair class)

and then, convert C++ code to C# code from the blog:
https://github.com/yinlinglin/LeetCode/blob/master/SudokuSolver.h

Excellent code in C++, using class for node on the board. Learn a few things, fun to play with the code

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program3.cs

solution 4:
https://github.com/jianminchen/sudokuSolver/blob/master/Program4.cs
source code from the blog:
https://github.com/xiaoxq/leetcode-cpp/blob/master/src/SudokuSolver.cpp

Solution 5:
read the blog: (Good coding! practice more based on this blog)
https://github.com/zwxxx/LeetCode/blob/master/Sudoku_Solver.cpp

and convert the C++ code to C# code, (great workout on C# LinkedList for blank nodes)

https://github.com/jianminchen/sudokuSolver/blob/master/Program5.cs

Solution 6:
read the blog:
http://shanjiaxin.blogspot.ca/2014/04/sudoku-solver-leetcode.html

and convert Java code to C# code, great workout on C# and logic checking "return false"

https://github.com/jianminchen/sudokuSolver/blob/master/Program6.cs

Solution 7:
blog:
http://www.jiuzhang.com/solutions/sudoku-solver/
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program7.cs

Solution 8:
Thanks for the blog's highlight line of code on back tracking; finally, I got it! My logic thinking has flaws on back tracking; extra backtracking is not a good. Minimize the back tracking, only do it when "return false". It makes sense to do that.

blog:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-valid-sudoku-sudoku-solver.html
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program8.cs

Solution 9:
blog:
http://www.cnblogs.com/TenosDoIt/p/3800485.html

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program9.cs

Solution 10:
blog: (Excellent implementation! no extra line or number in the code! Best for memorization! Go through other solutions later. )
https://github.com/rffffffff007/leetcode/blob/master/Sudoku%20Solver.java

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program10.cs

算法理解了, 代码可以记住了; 开始看不同的题解, 看看高手的代码; 从不同的题解中, 模仿模仿! 像打网球, 多接触不同的打法, 开阔眼界; 接着看这道题的题解. 试着从不同角度看一个问题, 多练习改代码; 看自己能不能有自己的看法, 去尝试一点更改, 玩一点花样; 增加练习C#编程的机会.

Also, the code written has been work on readability, learned through my favorite book reading:
http://shop.oreilly.com/product/9780596802301.do

Those favorite rules I like to learn, pick up and follow:
Big fan of DRY (Do not repeat yourself) principle, do one thing a time, break giant expression, using explaining variable or summary variable, and abstract the thing to a function, extract a subproblem to a function. The code is also modified to fit into short memory, less mental baggage to read through. 



Read solutions:

https://github.com/jordandong/myleetcodes/blob/master/SudokuSolver.cpp

https://github.com/Sayericplz/myleetcode/blob/master/isValidSudoku.cpp


BFS, using queue - try to convert it to C#
http://yucoding.blogspot.ca/2013/12/leetcode-question-sudoku-solver.html

Leetcode: N puzzle queens

Read the blogs, and understand the algorithm first:

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

http://www.acmerblog.com/leetcode-solution-n-queens-6254.html
 
http://blog.csdn.net/feixiaoxing/article/details/6877965

and later, wrote the program using C#, share the code:

Algorithm: Eight puzzle queen

https://github.com/jianminchen/eightPuzzleQueen/blob/master/Program.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/51NQueenProblems.cs

January 12, 2016

Review the algorithm again. The following blog gives a good explanation, help me understand the algorithm better.

http://blog.csdn.net/linhuanmars/article/details/20667175

http://buttercola.blogspot.ca/search/label/Leetcode

http://yucoding.blogspot.ca/2013/01/leetcode-question-59-n-queens.html

https://polythinking.wordpress.com/2013/02/27/leetcoden-queens-i-and-ii/

It is fun to read solutions in C++/Java.