When I first tried to learn the algorithm, I was very impressed with two algorithms, one is dynamic programming, and the other is backtracking algorithm. If it is said that the art of algorithmic thinking, it is attributed to dynamic programming; but if it is said that the art of using computer execution mechanisms to solve problems, it is none other than the backtracking algorithm. I also sincerely admire that computers can still perform this way.

What is a backtracking algorithm? What problem can it solve? With these two questions, and then using examples to answer these questions is the purpose of this chapter.

The backtracking algorithm is based on recursion. Although the execution mechanism of recursion has been explained in detail in Chapter 4, the examples are all simple single recursive forms. Therefore, this chapter first reviews the recursion, and then progresses layer by layer, and finally until the `N`

queen of the representative problem of backtracking is solved , gradually and thoroughly understand the backtracking algorithm. Let’s talk less, let’s get to know such a cool algorithm.

I think everyone hopes that they have the ability to go back in time. If they chose to chase her bravely at that time, maybe there is no regret now? If you could study hard at that time, you wouldn't be stuck with your academic qualifications now? If you listened to your parents to stay in your hometown, you wouldn't be so tired now, right? Behind every choice is the possibility of discarding other choices, that is, the **opportunity cost of** choice .

Going back to the algorithm, is it possible that I did all the above three choices, and finally I compared the results after they were selected and chose the most satisfactory one. can! Backtracking is precisely an algorithm that can try every possibility. This is a **brute force search algorithm** . It can try every different branch of the problem. Not to mention the crossroads of life, it is the intersection of the rice word. I also put each kind of The result is clear to you.

Backtracking algorithm can perform brute force search, so what exactly can it solve?

The problems it solves are problems that require violence `-_-#`

. Here are six common types of problems that can be solved retrospectively.

For example, please give `[1, 2, 3, 4]`

each possibility of the combination of numbers . The result is `[12, 13, 14, 23, 24, 34]`

that because the `23`

sum `32`

is a combination, it is ignored `32`

. If you say this is the short answer, using a loop can be resolved, and that a change in title conditions, the figures given `1 - 20`

each between `12`

the possibility of a combination of species, then traverse not so that.

Given `[1, 2, 3]`

all the possibilities of permutation, the result is `[123, 132, 213, 231, 312, 321]`

.

Given `[1, 2, 3]`

the possibility of all subsets of numbers (power sets), the result is `[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]`

.

Given a string of numbers `25525511135`

, return all `IP`

the possible forms of the address format, and the result is `["255.255.11.135", "255.255.111.35"]`

.

For question types , please refer to Likou `200`

Island and `547`

Moments of Friends, which will be introduced in detail later.

Please refer to `8`

Solving Sudoku and Queen’s Questions for the type, which will be introduced in detail later.

The above-mentioned six types may look quite different, but in fact they are all of the

tree-type problemtype, and we will explain the way when we explain the specific problems.

Because backtracking is based on recursion, it can also be said that backtracking is recursion, but recursion is a more complicated call, so we still use two topics to re-understand the recursive call.

Give you an array of nums, please return the dynamic sum of nums. Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: The dynamic and calculation process is [1, 1+2, 1+2+3, 1+2+3+4]. Source: LeetCode Link: https://leetcode-cn.com/problems/running-sum-of-1d-array

Simply put, it is the process of sequential accumulation. The sum of each number is equal to the sum of all the elements before it plus itself. Use a traversal solution from front to back:

var runningSum = function (nums) { for (let i = 0; i <nums.length-1; i++) { nums[i + 1] = nums[i + 1] + nums[i] } return nums };

At this point we began to toss, if we use recursion, how to solve this problem? In fact, the above description: the **sum of each number is equal to the sum of all the elements before it plus the sum of itself, which** has been disassembled for the sub-problems. So at this time, we can reverse it, the sum of the last number of the array is equal to all the sums before it plus itself, and then reverse it in turn, the code is as follows:

var runningSum = function (nums) { const _helper = end => { if (end === 0) {//To the beginning of the array, start returning return nums[0] } nums[end] = _helper(end-1) + nums[end]//the element before it plus itself return nums[end]//return the calculated result } _helper(nums.length-1)//start from the last number return nums };

This is the simplest single recursive call, which means that the recursive function only calls itself once. Next, let's look at the problem of calling itself twice.

The number n represents the logarithm of generating parentheses. Please design a function that can generate all possible and valid parentheses combinations. Input: n = 3 Output: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Source: LeetCode Link: https://leetcode-cn.com/problems/generate-parentheses

According to the meaning of the question, the final length must be `2n`

, and the number of left and right parentheses are respectively `n`

, and the left parenthesis must be used as the start of the valid parenthesis. Only when the remaining number of the right parenthesis is greater than the left parenthesis can it be placed. Code, I drew an execution sequence diagram, let's compare it:

var generateParenthesis = function (n) { const ret = []//store a valid set of brackets const _helper = (left, right, parenthesi) => { if (left === 0 && right === 0) {//When the number of left and right parentheses is used up ret.push(parenthesi)//found a valid set } if (left> 0) {//The rule of putting the left parenthesis: when there is a left parenthesis, it can be placed _helper(left-1, right, parenthesi +'(')//reduce the number of left parentheses } if (right> left) {//Rules for putting right parentheses: only when the remaining number of right parentheses is greater than the left parenthesis can be placed _helper(left, right-1, parenthesi +')')//reduce the number of right parentheses } } _helper(n, n,'')//Pass in the remaining number of left and right parentheses return ret };

The gray node in the figure is a partial pruning operation, because as long as the brackets are added according to the gray node, the subsequent generation must be non-compliant, so the subsequent recursion can be directly performed in the code.

There is a recursive function calls itself twice, first to add a left parenthesis perform recursive, when the left parenthesis has been done adding, and then begin a recursive add a right parenthesis, to observe the **first 6step to the second 7step of the jump** , because Recursion is to call itself twice, the

`2`

step to the first `3`

step`7`

step to perform another possibility, Each subsequent function follows this rule, which is also a recursive execution mechanism.It is not difficult to find that when **the possibility of each step of the** recursion **is twice, the final execution order generates a binary tree** . The depth of the recursion depends on the length of the final result. The result is the `2n`

length, so the depth is `2n`

.

What is the backtracking algorithm? That is, the possibility here is

`2`

replaced by`n`

second, so that the binary tree will become a`n`

fork tree, and another operation will be performed after each recursion. At this time, it is the time for the post-order traversal of the tree to be executed.

Combination arrangements often appear together, here is a brief explanation of their differences.

What is a combination? Assuming there are three stars `abc`

and three fans `xyz`

, `2`

how many choices are there for each fan to choose a recognized star? Obviously , it doesn't matter whether the fans choose `ab`

or `ba`

. In the final result, the two choices are the same, so this is a combination problem.

What is permutation? Or if there are three stars `abc`

and three fans `xyz`

, let each fan choose the `1`

place and `2`

place you think , how many ways are there to choose? Obviously, the `ab`

sum `ba`

is two different results at this time, and both need statistics. This is the arrangement problem.

Given a string containing only numbers 2-9, return all letter combinations it can represent. The mapping of numbers to letters is given as follows (same as phone buttons). Note that 1 does not correspond to any letters. Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] Source: LeetCode Link: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

Taking input `23`

as an example, it is to extract the `2`

corresponding ones `abc`

separately and combine them with the `3`

corresponding ones `def`

. We need an auxiliary function to help us with this. What it does is to take out the letter corresponding to the number, use the extracted letter to combine the letter corresponding to the next number, and finally find all combinations.

When is a combination that meets the requirements found? When the length of this combination is equal to the length of the input number, even one is found.

Because each number represents `3`

a letter on average , when recursively represents the execution tree, it will be a trinomial tree. What is the depth of the recursion? It depends on the number of digits entered. For example, when `27465`

five digits are entered , the depth of the final execution tree is the `5`

level.

code show as below:

const letterCombinations = digits => { if (digits ==='') {//When entering an empty string return []//return empty collection } const ret = []//used to store all found combinations const letterArr = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'] //Store the alphabet corresponding to the number const _helper = (start, s) => {//helper function if (s.length === digits.length) {//found a combination ret.push(s) return//return to the previous level of recursion } const letters = letterArr[digits[start]]//corresponds to abc, def for (let i = 0; i <letters.length; i++) { _helper(start + 1, s + letters[i])//perform multiple recursion } } _helper(0,'') return ret };

The parameters passed in `start`

represent the subscripts of the input numbers that need to be processed in sequence. As `23`

an example, first deal with the problem of subscripts, `0`

which is the `2`

corresponding letter. When entering the next layer of recursion, `+ 1`

it is to deal `3`

with the problem of corresponding letter combinations.

What is passed in `s`

represents the current combination, and each time it enters the next layer of recursion `s + letters[i]`

, it takes the results of this layer to the next layer. Even if this layer meets the requirements of the combination, the result is saved under the recursive termination condition of the next layer, then the recursion is terminated, and the recursion of the previous layer is returned.

Because the recursion of each layer is the execution `n`

time of the loop , when the loop of this layer is executed, it will return to the previous layer.

Given two integers n and k, return all possible combinations of k numbers in 1...n. Example: Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,4],[2,3],[3,4]] Source: LeetCode Link: https://leetcode-cn.com/problems/combinations

After having the experience of solving the previous combination problem, we directly go to the execution tree, and then explain the similarities and differences of this problem, take `1 ... 4`

and `k`

as `2`

an example:

For example, `13`

and `31`

is the same combination, so when processing, we need to ignore `'相同'`

the combination, how to ignore the operation? Every time you enter the next layer of recursion, the initial traversal position can be carried out `+ 1`

. The rest of the logic is similar to the previous question, the code is as follows:

var combine = function (n, k) { if (n <0 || k <0 || k> n) {//Both n and k must meet the conditions return [] } const ret = [] const _helper = (start, arr) => { if (arr.length === k) { ret.push(arr) return } for (let i = start; i <= n; i++) {//i = start, ignoring numbers smaller than start for combination _helper(i + 1, arr.concat(i)) } } _helper(1, []) return ret };

This solution can indeed be passed, but good guys, this is too slow. The reason is that we enter the core logic of the next level of recursion:

_helper(i + 1, arr.concat(i))

Unexpectedly, `concat`

this method will be so slow. In fact, our purpose is nothing more than to add the current number `i`

to the array, and then bring it to the next level of recursion, so we can use the `push`

method.

At the same time, it is not difficult to find from the execution tree. When you finally find another combination, you need to pop the end of the previous combination, and you need to leave a place. Therefore, after each cycle, we perform pop-up and leave-position operations. The optimization is as follows:

var combine = function (n, k) { if (n <0 || k <0 || k> n) { return [] } const ret = [] const _helper = (start, arr) => { if (arr.length === k) { ret.push([...arr])//need to be copied return } for (let i = start; i <= n; i++) { arr.push(i) _helper(i + 1, arr) arr.pop() } } _helper(1, []) return ret };

When a matching combination is found in the termination condition, we need to make a copy, because each layer of the loop has `arr.pop()`

operations, which will eventually affect all the collected combinations. Take a look at the optimized results:

Given an array candidates with no duplicate elements and a target number target, Find out all combinations of candidates that can make the number sum as the target. The numbers in candidates can be repeatedly selected without limitation. Description: All numbers (including target) are positive integers. The solution set cannot contain repeated combinations. Input: candidates = [2,3,6,7], target = 7, The solved set is: [[7], [2,2,3]] Source: LeetCode Link: https://leetcode-cn.com/problems/combination-sum

There are several key information in this question. The first is that there is an additional `target`

target value. That is to say, the value of our statistics needs to be compared with this target value. A useful operation for comparison is `candidates`

to sort first . In this case You can save the calculation result and just add and subtract based on it.

Another piece of information is that you can use a certain number in the array without restriction. This operation will be very convenient after sorting. Start counting the possibilities of each combination directly from the smallest number.

The rest of the problem-solving framework is similar to the previous one. We write the code as follows:

var combinationSum = function (candidates, target) { candidates.sort((a, b) => a-b) const ret = [] const _helper = (start, sum, arr) => { if (sum> target) {//Because it is sorted, the sum will only be bigger next return } if (sum === target) {//just found ret.push([...arr]) return } for (let i = start; i <candidates.length; i++) { sum += candidates[i]//sum is the calculation result arr.push(candidates[i])//arr stores a temporary set _helper(i, sum, arr)//Note that the first parameter does not have +1, because it needs to be used infinitely sum -= candidates[i] arr.pop() } } _helper(0, 0, []) return ret };

There are two recursive end conditions. If it is greater than that, the current layer of recursion is ended. After the end `sum -= candidates[i]`

, `candidates[i]`

the non-compliant or used value is subtracted , and then it pops up `candidates[i]`

and enters the next loop.

In fact, the idea of solving the problem is the same as that of the previous question, except that there are some more restrictions on the problem.

We have not analyzed the complexity of the backtracking algorithm yet, here is a brief explanation. In fact, it is not difficult to find from the previous topic that the complexity of the backtracking algorithm is very high. For example `17`

, if you enter `5`

a number, then the node at the bottom level of the final execution tree expansion is `3 * 3 * 3 * 3 * 3`

one, and this data scale is exponential `O(2ⁿ)`

. Therefore, when processing big data, backtracking has very high requirements for computer computing performance, and the backtracking algorithm also has its own pruning operation to reduce the amount of unnecessary calculations.

The topic of backtracking algorithm is very broad, and the remaining several types of questions will be explained in the next chapter.

Reference: https://cloud.tencent.com/developer/article/1754431 Frontend Data Structure and Algorithm (13): 01 The Art of Execution-Backtracking Algorithm (Part 1)-Cloud + Community-Tencent Cloud