Like attention, no more lost, your support means a lot to me!

🔥 Hi, I’m Chouchou. GitHub · Android-Notebook has been included in this article. Welcome to grow up with Chouchou Peng. (Contact information at GitHub)

preface

  • The idea of backtracking algorithm is not complicated, but many variations on the basis of backtracking are also frequently tested in interviews, so it is very important to master the basic framework of problem solving.
  • In this article, I will sort out the basic concept of backtracking algorithm & common test type. Please be sure to like and follow if you can help, it really means a lot to me.

series

  • The algorithm of interview questions | problems summary list”
  • The algorithm problem of intersection and cyclization interview questions | chain table”
  • The interview questions | back algorithm problem solving framework
  • Interview questions | and check the data structure set & joint – search algorithms,
  • The interview questions | binary tree data structure foundation”

Extension of the article

  • Algorithm of interview questions | buildings with eggs (from Google interview questions)
Permutation & combination & subset problem Hint & problem solving
46. The whole arrangement

Permutations		 “Antithesis”
47. Full permutation II

Permutations II		 “Antithesis”
39. Sum of combinations

Combination Sum		 “Antithesis”
40. Sum of combinations

Combination Sum II		 “Antithesis”
78. The subset

Subsets		 “Antithesis”
90. The subset II

Subsets II		 “Antithesis”
784. Letters are arranged in all case

Letter Case Permutation		 “Antithesis”
386. Dictionary order number

Lexicographical Numbers		 “Antithesis”
17. Alphabetic combinations of telephone numbers

Letter Combinations of a Phone Number		 “Antithesis”
22. Parenthesis generation

Generate Parentheses		 “Antithesis”


Lexicographical arrangement Hint & problem solving
31. Next permutation

Next Permutation		 “Antithesis”
60. Permutation K

Permutation Sequence		 “Antithesis”
440. The KTH smallest digit in lexicographical order

K-th Smallest in Lexicographical Order


Two-dimensional plane search Hint & problem solving
79. Word search

Word Search		 “Antithesis”
212. Word Search II

Word Search II


Flood Fill Hint & problem solving
733. Image rendering

Flood Fill		 “Antithesis”
200. Number of islands

Number of Islands		 “Antithesis”
130. The surrounding area

Surrounded Regions		 “Antithesis”
44. Wildcard matching

Wildcard Matching
10. Regular expression matching

Regular Expression Matching
488. Zuma Game

Zuma Game
529. Minesweeper

Minesweeper


other Hint & problem solving
51. The N queens

N-Queens
52. Queen II

N-Queens II
37. Hard alone

Sudoku Solver
301. Delete invalid parentheses

Remove Invalid Parentheses
Minimum number of invalid parentheses removed

Minimum Remove to Make Valid Parentheses

directory

1. An overview of the

1.1 Retrospective thought

Backtrack algorithm is a trial-and-error idea, which is depth first search in essence. That is, starting from one state of the problem, try the options available to the current state in turn to enter the next state. Recursion is a process in which if there are no more choices to be made in a certain state, or if the desired answer has been found, one step or more steps back and try again until finally all the choices have been tried.

The whole process is like a maze. When we come to a fork in the road, we can choose to go in one direction. If you reach a dead end, go back to the last fork and continue trying in the other direction until there is no exit or you find one.

1.2 Three elements of backtracking

After understanding the idea of backtracking algorithm, let’s analyze the key points of backtracking. In the backtracking algorithm, three elements need to be considered: path, selection list and ending condition. Take maze running as an example:

  • 1. Path: The choice that has been made
  • 2. Selection list: Options available in the current state
  • 3. End condition: The list is empty, or the target is found

To get out of this maze, we need to do the same thing over and over again: choose to try it in one direction. If you reach a dead end, go back to the last fork and continue in the other direction. With the program to achieve, this repeated thing is recursive function, in practice we can follow a solution template & ideas:

Fun backtrack(){1. Check whether the current state satisfies the termination condition if(termination condition){return solution} 2. Otherwise iterate over the selection list for(select in select list){3. Make the selection solution. Push (select) 4. Backtrack () 5. Backtrack (undo selection) stack.pop(select)}}Copy the code

It should be noted that the problem solving framework & thinking is not rigid and should be analyzed according to specific problems. For example, backtracking (undo selection) is not necessary. In section 3.2 (k sorting), and in Section 5 (number of islands), they are not necessary to backtrack after the deep function returns.

1.3 Back pruning

Because of the high time complexity of backtracking algorithms, when we encounter a branch, we should not attempt to go down this path if we have the “foresight” to know that a choice will not be found in the end, a step called prune.

So how do you find this “prescience”? After my summary, there are probably the following situations:

  • Repeat state

Permutations II this problem, given a sequence that can contain repeated numbers, requires that all non-repeated Permutations be returned, for example, the inputs for [1,1,2] expect the output to be [1,2], [1,1], [2,1]. Using the template we introduced earlier, this problem is not difficult:

class Solution { fun permute(nums: IntArray): List<List<Int>> {val result = ArrayList<List<Int>>() // Select List val useds = BooleanArray(nums.size) {false} // path val Track = LinkedList<Int>() fun backtrack() {if (track.size == nums.size) {result.add(ArrayList<Int>(track)) return } for ((index, used) in useds.withIndex()) { if (! Track.push (nums[index]) useds[index] = true backtrack() // Trace.pop () useds[index] = false}}} backtrack() return result } }Copy the code

However, since there are two 1’s in the original array, there will be some duplicate permutations in the result. One way to do this is to check if the result set already has the same permutation after you get the permutation, which is an O(n2)O(n^2)O(n2) comparison, which is obviously not wise. Another approach is to look for repetitive states and “presciently” avoid some choices in the first place.

So let’s talk about what is a repeated state? Remember we talked about the three elements of backtracking: path, selection list, end condition. In general, the end condition is fixed among the three elements, and the path and selection list change with each selection & backtracking.

That is, when we find that the paths and selection lists of two states are exactly the same, the two states are exactly the same. If you recurse from two repeated states, the final result will be the same. In this case, we first perform a quick sort of the input. Before each subsequent selection, we first determine whether the current state is the same as the previous selection. If yes, we skip it.

class Solution { fun permuteUnique(nums: IntArray): List<List<Int>> { val result = ArrayList<LinkedList<Int>>() if(nums.size <= 0){ result.add(LinkedList<Int>()) return Array.sort (nums) val used = BooleanArray(nums.size){false} If (track.size >= nums.size){result.add(LinkedList<Int>(track)) return} for((index,num) in nums.withIndex()){ if(used[index]){ continue } if(index > 0 && ! Used [index-1] && nums[index] == nums[index-1]){continue} used[index] = true track.push(num) // Recursion Backtrack () // Backtrack used[index] = false track.pop()}} backtrack() return result}}Copy the code
  • Final solution determination

Once we have determined the final solution in one of the selected branches, there is no need to try other alternatives. For example, in 79. Word Search, there is no need to continue the Search once the Word is certain to exist, which is the subject of section 4.

fun backtrack(...) {for (select in select list) {1. Val match = backtrack(...) If (match) {return true}}Copy the code
  • Invalid selection

There’s no point in trying a choice when we know that we can’t find the final solution. For example, 39. Combination Sum, 60. Permutation Sequence

3. Permutation & combination & subset problem

3.1 Permutation & combination problem

Permutation, combination and subset are the most common problems in backtracking algorithms. Among them, subset problem is also combinatorial problem in nature. Let’s take you through a simple question to understand the difference between permutation and combination:

  • Permutation problem:

I have three different balls A, B, and C, and I take two of them and I put them in A row. How many ways can I do that?

  • Combination problem:

I have 3 different balls A, B, and C, and I take 2 of them and put them in A pile. How many ways can I do that?

What’s the difference between a row and a pile? Obviously, a row is sequential, and a pile is non-sequential. For example, [A B C] and [A C B] are different, while {A B C} and {A C B} are the same.

From the above figure, it can be clearly seen that the combination problem is to remove the repeated set on the basis of the permutation problem; Subset problems are combinatorial problems of different sizes.

So, how do you exclude sets that have the same elements in a different order? Here is a very easy to understand method, I believe that many students will be enlightened: “my junior high school math teacher taught me this.”

As you can see, repetition can be avoided by avoiding combining previous elements. For example, after {B,}, do not combine the previous elements of A, otherwise there will be duplication. Because {A, B} combinations already exist in the {A,} branch. Therefore, we can use a FROM variable to indicate the range of selections allowed in the current state.

The permutation and combination code of the number k from n is given below. Since the code of the recursive solution is more explanatory, readers should give priority to ensure that they can write the recursive solution skillfully:

Complexity analysis:

  • The whole arrangement

A total of n! n! n! Subproblems, the time complexity of each subproblem is O(n)O(n)O(n) O(n), so the total time complexity n∗n! n*n! N ∗ n! . Except for the output array, the space complexity is O(n)O(n)O(n).

  • combination

There are a total of 2n2^n2n subproblems, each of which has a time complexity O(n)O(n)O(n) O(n), so the total time complexity n∗2nn*2^nn∗2n. Except for the output array, the space complexity is O(n)O(n)O(n).

3.2 Lexicographical ordering

There is also the concept of Dictionary order, which is based on alphabetical order, similar to the order of words in A Dictionary, for example [A B C] comes before [A C B]. To obtain the full arrangement of lexicographic order, both recursive and non-recursive solutions can be achieved.

Using the recursive solution, you only need to ensure that the selection list is sorted alphabetically, resulting in lexicographical sorting, which is relatively straightforward to implement, as explained in Section 1.4.

The basic idea of the non-recursive solution is to start from the current string and find the next lexicographic permutation, for example, from [A B C] to [A C B]. So how do you do that? You can think about this a little bit:

  • Next permutation

To rearrange a given sequence of digits into the Next larger Permutation in a lexicographical order.

Once you understand the algorithm for the next permutation, it is not difficult to write the algorithm for the full permutation. You just print the next permutation from the first permutation, and you end up with a lexicographic complete permutation. If you are interested, you can check it out in the solution in the previous section, so I won’t post it here.

  • The KTH permutation

In addition to finding the next permutation, finding the KTH permutation is very common. For example: 60. The KTH Permutation Sequence, 440. K-th Smallest number in Lexicographical Order. The basic idea is to know the number of leaf nodes in this branch in advance by calculating factorial, and prune if K is not on this branch:

4. Two-dimensional plane search problem

The maze problem mentioned at the beginning of the article is actually a backtracking algorithm problem on the two-dimensional plane. The current position is the end point when the termination condition is terminated. Since it is a backtracking algorithm, there is no escape from the three elements we emphasize over and over again: path & selection list & termination condition:

4.1 Path – TWO-DIMENSIONAL array USeds

In the full permutation problem, we use a one-dimensional Boolean array, used, to mark paths already traveled. Similarly, in a two-dimensional plane, we need to use a two-dimensional Boolean array to mark the path we’ve taken.

1. Int [] useds 2. Int [] USedsCopy the code

4.2 Select list-offset array

When searching on a two-dimensional plane, the selection list of a point is its up, down, left, and right directions (except the direction from which it came). For coding purposes, you can use an array of offsets. The order of the four offsets in the array is irrelevant.

int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
Copy the code

4.3 Checking Boundaries

A two-dimensional plane is usually bounded, so you can write a function to determine if the current input position is out of bounds:

private boolean check(int row, int column) {
    return row >= 0 && row < m && column >= 0 && column < n;
}
Copy the code

Word Search 79.

5. Flood Fill problem

Flood Fill (or Seed Fill) is an advanced version of the two-dimensional planar search problem in the previous section. That is, to find the connected nodes that meet the conditions on the two-dimensional plane.

The so-called connected node refers to two nodes connected in four directions. Some problems expand to eight directions (four diagonal directions), but only a few more directions, not much difference. For example, the following image colors the white squares where the central nodes are connected:

The entire problem solving framework and the last section of the two-dimensional planar search problem Same, here another solution: emphasis on and check set, in this article, we have explained in detail and check the set of usage scenarios and problem solving skills, interview questions | and check the data structure set & joint – search algorithms,

Simply put: The parallel search set is suitable for dealing with the connectivity problem of disjoint sets, which is also suitable for solving the connectivity problem of Flood Fill. We can combine the nodes connected to the central node into the same component. After all processing is completed, we can judge whether the two nodes are connected by querying and looking up the set:

Tip: The time complexity of the query is close to O(1)O(1)O(1)

6. Summary

The idea of backtracking algorithm is not complicated, but it does have high frequency. A good command of backtracking algorithm is also helpful for understanding dynamic programming algorithm, which is of high learning priority.

The resources

  • Backtracking — Wikipedia

  • Flood Fill — Wikipedia

  • Introduction to backtracking algorithms + exercises (all permutations I). By liweiwei

  • Backtracking search + pruning (all permutations II) by liweiwei

  • Using backtracking on a two-dimensional plane (word search I). By liweiwei

  • Backtracking algorithms by liweiwei

  • A Detailed explanation of backtracking algorithms by Labuladong

  • Detailed Analysis and Application of FloodFill Algorithm — By Labuladong

  • Interview with algorithms in 300 Minutes, produced by Liguo & Dragoo.com

Recommended reading

  • Cryptography | is Base64 encryption algorithm?
  • Java | show you understand the ServiceLoader principle and design idea
  • Use annotations Java | this is a comprehensive strategy (including the Kotlin)
  • Java | reflection: access type information at run time (including the Kotlin)
  • Android | interview will ask Handler, are you sure you don’t look at it?
  • Android | show you understand NativeAllocationRegistry principle and design idea
  • Computer composition principle | Unicode utf-8 and what is the relationship?
  • | why floating-point arithmetic of computer constitute principle is not accurate? (Ali written test)

Creation is not easy, your “three lian” is chouchou’s biggest motivation, we will see you next time!