Front end data structure and algorithm (13): 01 The Art of Execution-Backtracking Algorithm (Part 1)

Front end data structure and algorithm (13): 01 The Art of Execution-Backtracking Algorithm (Part 1)

Preface

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 Nqueen 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.

What is a backtracking 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.

What problem can the backtracking algorithm solve?

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.

1. Combination problems

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 23sum 32is 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 - 20each between 12the possibility of a combination of species, then traverse not so that.

2. Arrangement problem

Given [1, 2, 3]all the possibilities of permutation, the result is [123, 132, 213, 231, 312, 321].

3. Subset problem

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]].

4. Segmentation problem

Given a string of numbers 25525511135, return all IPthe possible forms of the address format, and the result is ["255.255.11.135", "255.255.111.35"].

5. FloodFill coloring problem

For question types , please refer to Likou 200Island and 547Moments of Friends, which will be introduced in detail later.

6. Checkerboard problem

Please refer to 8Solving 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 problem type, and we will explain the way when we explain the specific problems.

Understand recursion again

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.

1480-The dynamic sum of a one-dimensional array↓

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.

22-Bracket generation ↓

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 first 2step to the first 3step is only to perform one of the possibilities, because it is a depth-first traversal, when this possibility has been executed, you need to jump to the first 7step 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 2nlength, so the depth is 2n.

What is the backtracking algorithm? That is, the possibility here is 2replaced by nsecond, so that the binary tree will become a nfork 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 problem

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

What is a combination? Assuming there are three stars abcand three fans xyz, 2how many choices are there for each fan to choose a recognized star? Obviously , it doesn't matter whether the fans choose abor 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 abcand three fans xyz, let each fan choose the 1place and 2place you think , how many ways are there to choose? Obviously, the absum bais two different results at this time, and both need statistics. This is the arrangement problem.

17-Letter combination of phone number ↓

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 23as an example, it is to extract the 2corresponding ones abcseparately and combine them with the 3corresponding 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 3a 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 27465five digits are entered , the depth of the final execution tree is the 5level.

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 startrepresent the subscripts of the input numbers that need to be processed in sequence. As 23an example, first deal with the problem of subscripts, 0which is the 2corresponding letter. When entering the next layer of recursion, + 1it is to deal 3with the problem of corresponding letter combinations.

What is passed in srepresents 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 ntime of the loop , when the loop of this layer is executed, it will return to the previous layer.

77-Combination ↓

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 ... 4and kas 2an example:

For example, 13and 31is 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, concatthis method will be so slow. In fact, our purpose is nothing more than to add the current number ito the array, and then bring it to the next level of recursion, so we can use the pushmethod.

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:

39-combined sum

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 targettarget value. That is to say, the value of our statistics needs to be compared with this target value. A useful operation for comparison is candidatesto 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.

At last

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 5a number, then the node at the bottom level of the final execution tree expansion is 3 * 3 * 3 * 3 * 3one, 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