This is the 11th day of my participation in Gwen Challenge
Recently, I want to sort out my experience of brush algorithm. On the one hand, I want to review and consolidate. On the other hand, I also hope that my sharing can help more friends in learning algorithm.
The column is called “Algorithm Tips”, which will focus on the entirety of the algorithm, but will not cover all aspects. It is suitable for people with some algorithm experience to read.
This time we will focus on backtracking. All the questions and source code of this section are uploaded to github, and the solution is mainly implemented in Python.
An overview of the
In the last article, we focused on the solution of recursion, but in fact, in the process of using recursion, we will find that many problems also use the idea of backtracking. In fact, there is no essential difference between recursion and backtracking, both of which break down a given problem into subproblems.
Backtracking uses the idea of trial and error, which attempts to solve a problem step by step. In the process of step solution, when it tries to find that the existing step solution can not get an effective and correct solution, it will cancel the calculation of the previous step or even the previous steps, and then try to find the answer of the problem again through other possible step solution.
Backtracking is usually done using the simplest recursive method, and two things can happen after repeated steps:
- Finding a possible correct answer;
- After all possible steps have been tried, the question is declared unanswered.
In the worst case, backtracking results in an exponential time calculation.
Next, let’s take a look at some of my favorites.
78. The subset
This problem comes from 78.subset.
You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.
The solution set cannot contain duplicate subsets. You can return the solution set in any order.
Example 1: input: nums = [1, 2, 3] output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Copy the codeSo just to get a sense of this, for each element in the array, you can choose, you can choose not to choose, there are two possibilities, n elements is 2 to the n choices.
Each time an element is selected or not selected, the recursion continues. The action of selecting or not selecting can be coordinated by backtracking.
See the code below for the answer.
class Solution:
def subsets(self, nums: List[int]) - >List[List[int]] :
def _dfs(cur, index) :
# cur is the current result, and index is the traversal index
If the traversal index reaches the end, the current result is stored
if index == len(nums):
res.append(cur[:])
return
This step represents the element that uses the current index
cur.append(nums[index])
# continue recursing
_dfs(cur, index+1)
# traceback to pop the current element
cur.pop()
# continue recursing
_dfs(cur, index+1)
res = []
_dfs([], 0)
return res
Copy the code17. Alphabetic combinations of telephone numbers
Now, while the iron is hot, look at this one. 17. Alphabetic combinations of telephone numbers.
Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order.
The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.
Example 1: input: who = "23" output: [" AD ", "ae", "af", "bd", "be", "bf", "CD" and "ce", "cf"]Copy the codeThis problem also uses backtracking. The backtracking of the previous problem is reflected in selecting or not selecting each element, while this problem has multiple possibilities for each element. For example, 2 corresponds to ABC.
The solution is as follows:
class Solution:
def letterCombinations(self, digits: str) - >List[str] :
if not digits:
return list()
phoneMap = {
"2": "abc"."3": "def"."4": "ghi"."5": "jkl"."6": "mno"."Seven": "pqrs"."8": "tuv"."9": "wxyz",}def backtrack(index: int) :
if index == len(digits):
res.append("".join(combination))
else:
digit = digits[index]
for letter in phoneMap[digit]:
combination.append(letter)
backtrack(index + 1)
combination.pop()
combination = list()
res = list()
backtrack(0)
return res
Copy the code51. The N queens
Next, let’s look at the super classic backtracking problem, queen 51.n.
The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other.
Given an integer n, return the number of different solutions to the queen of N problem.
Example 1: Input: n = 4 Output: 2 Explanation: As shown in the figure above, there are two different solutions to the 4-queen problem.Copy the codeThis is a difficult problem, but once we understand backtracking, it’s not that complicated.
The idea is to go through every line, trial and error. Now, the tricky part of this problem is how to determine what is a feasible set of solutions. My method is to use three sets to store the vertical, prime and na coordinates that have been traversed. If they are inside, they are not feasible.
Here’s my code:
class Solution:
def __init__(self) :
self.res = 0
def totalNQueens(self, n: int) - >int:
col, pie, na = set(), set(), set(a)def _dfs(level) :
if level == n:
self.res += 1
return
for j in range(0, n):
if j in col or level + j in pie or level -j in na:
continue
col.add(j)
pie.add(level +j)
na.add(level-j)
_dfs(level + 1)
col.remove(j)
pie.remove(level +j)
na.remove(level-j)
_dfs(0)
return self.res
Copy the code473. Matches make a square
Finally, let’s use this problem to reinforce. 473. Matches make a square
Remember the fairy tale “The Little Match Girl”? Now, you know how many matches the little girl has, please find a way to make a square using all the matches. Matches can’t be broken, they can be joined together, and each match must be used.
Enter the number of matches the little girl has, each match represented by its length. The output is whether you can form a square with all the matches.
Example 1: Input: [1,1,2,2] Output: trueCopy the codeI once encountered this problem in an interview. At first, I wanted to use greed, but failed to solve it. Later, I realized that I needed to use backtracking.
The perimeter of a square is determined, so the length of each side is determined, taking [1,1,2,2,2] as an example, the length of the side is 2.
Prepare an array of four edges, such as [2,2,2,2]. After the nums elements are iterated, the result is [0,0,0,0].
I made some optimizations in the algorithm. The first is the greedy idea of sorting the array from the largest to the smallest, generally speaking, it is easier to find the solution by hitting the larger matchstick first.
Another is pruning when traversing matchsticks. If two matchsticks are the same length, there is no need to iterate.
In short, this topic is used in the knowledge or very much, boundary judgment + recursion + backtracking + greedy + pruning, very test algorithm foundation, strongly recommended to do.
class Solution:
def makesquare(self, nums: List[int]) - >bool:
if not nums: return False
s = sum(nums)
If the perimeter is not divisible by 4, return False
if s % 4! =0: return False
w = s // 4
Sort the array from the largest to the smallest. This is a greedy way to find solutions much faster
nums.sort(reverse=True)
def _dfs(index, w_arr) :
The array must all be 0, otherwise return False
if index == len(nums):
return all([i==0 for i in w_arr])
result = False
for j in range(len(w_arr)):
If two consecutive values of w_arr are the same, you can skip it
if j > 0 and w_arr[j] == w_arr[j-1] :continue
# try to deduct nums[index]
if w_arr[j] >= nums[index]:
w_arr[j] -= nums[index]
if _dfs(index+1, w_arr):
return True
w_arr[j] += nums[index]
return result
return _dfs(0, [w,w,w,w])
Copy the code