For you must be before | backtracking algorithm 】【 ByteDance

I am participating in Nuggets Creators Training Camp # 4 (link: juejin.cn/post/706419…

Preface ✨

As a student who changed his major to 🥧, and because of the epidemic in the second semester of the freshman year, online courses at home are basically in the state of playing 🐟 for three days and drying for two days. Has always been a bit algorithmic (unknown fear). In the second semester of my sophomore year, I did not brush the algorithm until September last year. I have always used JS as the first language to learn algorithms, and I have gained a lot after one or two months of algorithm problem brushing. Maybe I have become more confident, and EVEN though SOME problems may not be solved for a while, I am still willing to settle down and quietly appreciate (learn from) a piece of code every day. Sometimes I have to sigh that good code will be as beautiful as poetry, and after reading some great god’s solution, I will have a feeling of enlightenment.

Solving a moderately difficult algorithmic problem is like climbing a mountain, and often it gives me more satisfaction than just the +1 I put into solving the problem. This process can be a lot more rewarding than we thought. ✨

Experience sharing

First of all, I am not a god. I want to share this article with others who are learning algorithms. Front-end learning is basically sticking together to warm up, learning and imitating is our innate ability. The author, as a beneficiary of the platform, now shares some of my personal experience with you, hoping it can be helpful to you.

The data of this paper came from CodeTop enterprise question bank

Emphasis:

More drawing
More drawing
More drawing

How to face their own problems, direct problem solving is sometimes more difficult to understand, the problem by drawing the way ✍ down, will let you do primary school mathematics in general 📕 to find rules, this habit is not only suitable for the retrospective algorithm introduced in this article. So stubborn friend happy 😎 must develop the habit of drawing!

(1) Backtracking to solve the problem ✨

1.1 Introduction to backtracking algorithm

Backtracking algorithm is actually a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will “backtrack” back and try another path. Backtracking is a kind of optimal search method, which searches forward according to the optimal conditions to reach the target. However, when a certain step is explored, it is found that the original choice is not good or fails to reach the target, so it takes a step back to make a new choice. The technology of going back and going again when there is no way is called backtracking method, and the point in a certain state that meets the backtracking condition is called “backtracking point”. Backtracking can be used for many complex, large-scale problems, and has the good name of being a “general solution.” — Baidu Encyclopedia

The essence of backtracking algorithm is a violent search process.

From a road to go forward, can enter into, can not enter back, another road to try again. An algorithm that doesn’t run into a wall

1.2 Main problems solved by backtracking algorithm

Combination problem:Find the set of k numbers in N numbers according to certain rules
Permutation problem:N numbers are arranged according to certain rules, and there are several ways to arrange them
Cutting problems:A string can be cut in several ways according to certain rules
Subset problem:How many subsets are there in a set of N numbers
Checkerboard problem:N Queen, solving sudoku and so on

1.3 Template of backtracking algorithm

The significance of the framework is to help us quickly set up the steps to solve the problem and reduce the situation that we have ideas but do not know how to start. Backtracking algorithms also have their own framework.

The backtracking algorithm can basically be viewed as an n-fork tree, with the horizontal axis representing the number of elements selected and the vertical axis representing the recursive process.

function backtrak(parameter){
    if(Recursive termination condition){// result.push() adds result set
        return
    }
    for(elementinSet){make a selection backtrack(current selection result) undo the selection// This step is the backtracking operation}}Copy the code

(2) Examples of backtracking algorithm

After we put in the above problem solving framework, and then through the way of drawing the steps presented, the backtracking algorithm will be easily solved. Let’s look at a few examples.

2.1 all arrangementForce buckle 46. Full alignment

2.1.1 Problem Description

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

Example 1:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

Example 2:

Input: nums = [0,1] output: [[0,1],[1,0]Copy the code

Example 3:

Input: nums = [1] Output: [[1]Copy the code

2.1.2 Problem analysis

The complete permutation problem of [1,2,3] is equal to the complete permutation of 1 + [2,3],2 + [1,3], and 3 + [1,2]

For the first choice we can choose one, two, threeThink carefully if this corresponds to the horizontal for loop described above
For the second selection, avoid selecting the element we selected the first timeThis is simply recorded in a map
By the time we get to the third one, we’ll knowRecursive termination conditions
Undo what you just selected, see if there are any other options, if there are no other options, continue to undo. (This step may be a little abstract, but you’ll understand when you see the code.)

The process that we just analyzed, the process of choosing from the first to the third, each time carries with it the result of this selection, is actually a recursive process.

Image credit: The Stupid Pig Demolition Team

2.1.3 the answer

var permute = function(nums) {
    const res = [] // Store all results
    const map = {} // Records whether the current element exists
    const dfs = (arr) = >{
        if(arr.length==nums.length){
            res.push(arr.slice()) // Make a shallow copy of the array so that subsequent operations on the array will not affect the res value
            return
        }
        for(const num of nums){ // traverse horizontally
            if(map[num]){ // This element is already selected
                continue
            }
            map[num] = true
            arr.push(num) // Select the element
            dfs(arr) / / recursion
            arr.pop() // Undo the selection
            map[num] = false 

        }
    }
    dfs([])
    return res
};
Copy the code

2.2 Restoring the IP AddressRestore the IP address

2.2.1 Problem Description

A valid IP address consists of four integers (each integer is between 0 and 255, and cannot contain a leading 0), separated by a hyphen (.).

For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, but “0.011.255.245”, “192.168.1.312” and “[email protected]” are invalid IP addresses. Given a numeric string s to represent an IP address, return all possible valid IP addresses that can be formed by inserting a ‘.’ into s. You cannot reorder or delete any digits in s. You can return the answers in any order.

Example 1:

Enter: s ="25525511135"Output:"255.255.11.135"."255.255.111.35"]
Copy the code

Example 2:

Enter: s ="0000"Output:"0.0.0.0"]
Copy the code

Example 3:

Enter: s ="101023"Output:"1.0.10.23"."1.0.102.3"."10.1.0.23"."10.10.2.3"."101.0.2.3"]
Copy the code

2.2.2 Problem Analysis

Horizontal for loops: How many can we select at most at a time?

According to the question, choose at most three and at least one at a time
The selected size ranges from 0 to 255
If the selection is greater than or equal to two digits, it cannot appear0X 0XXThat’s the case

Vertical recursion: Determine termination conditions

I have selected the IP address four times, but I have not finished selecting the IP address
The number of selected lengths exceeds the length of the entire IP address. Procedure

Select the way to record the subscript of the IP string using index value

Image credit: The Stupid Pig Demolition Team

The backtracking algorithm will exhaust all the nodesFind all possible combinations.

Then the answer

var restoreIpAddresses = function(s) {
    const res = [] / / the result set
     // ipArr stores every possible IP address, when its length is 4 recursive termination condition judgment
    const dfs = (ipArr,index) = >{ 
        if(ipArr.length==4) {if(index==s.length){// The length of the string is exactly equal to IP
                res.push(ipArr.join('. '))}// The recursion is terminated if the selection is not complete or the length exceeds the IP string length
            return
        }
        // Not finished yet
        for(let len=1; len<=3; len++){// Select one to three at a time
            if(len! =1&&s[index]=='0') return // When selecting 2-3 elements, do not start with '0'
            const ipChild = s.substr(index,len) // Intercepts the subIP address we selected just now
            if(+ipChild>255) return // Range restriction
            ipArr.push(ipChild) / / add
            dfs(ipArr,index+len)
            ipArr.pop() // backtrace (undo add)
        }

    }
    dfs([],0)
    return res
};
Copy the code

2.3 Combination SumForce buckle 39. Sum of combinations

2.3.1 Problem Description

Given an array of integer candidates with no duplicate elements and a target integer target, find all the different combinations that the candidates can make number and target, and return them as a list. You can return these combinations in any order.

The same number in the candidates can be selected repeatedly without limit. The two combinations are different if at least one number is chosen differently. For a given input, the number of different combinations of and for target is guaranteed to be less than 150.

Example 1:

Enter: candidates = [2.3.6.7], target = 7Output: [[2.2.3], [7]]
Copy the code

Explanation: 2 and 3 can form a set of candidates, 2 + 2 + 3 = 7. Note that 2 can be used more than once. 7 is another candidate. 7 is equal to 7. There are only two combinations.

Example 2:

Enter: candidates = [2.3.5], target = 8Output: [[2.2.2.2], [2.3.3], [3.5]]
Copy the code

Example 3:

Enter: candidates = [2], target = 1Output: []Copy the code

2.3.2 Problem Analysis

Question of the soul? : Will this question choose to use backtracking algorithm?

If you look at the common features of the problems, you’ll see that you can make choices every time, and the expansion of choices is an n-fork tree. For example, I choose [1,2, 3, 4] and then find that 3 does not meet the requirements. I need to go back to the state [1,2] before I choose again. When faced with this kind of problem, the problem usually requires a certain result set, not a number/Max/min condition. Intensive practice will help you quickly come up with backtracking algorithms when faced with these kinds of problems.

The solution to this problem is easier than the previous two, and the constraints are clear

Horizontal for loop:

You can select any element at a time (you can select it repeatedly)

Vertical recursion:

The recursion terminates when the selected sum is greater than or equal to the target value

[2,2, 2], [2,3,2], [2,3,2].

How do you do this? It’s very simple. You just put the initial index of an element.

2.3.3 the answer

var combinationSum = function(candidates, target) {
    const res = [] / / the result set
    const dfs = (start,path,sum) = >{
        if(sum>=target){ // Recursive termination condition
            if(sum===target){
                res.push(path.slice())
            }
            return
        }
        for(leti=start; i<candidates.length; i++){ path.push(candidates[i]) dfs(i,path,sum+candidates[i]) path.pop()/ / back
        }
    }
    dfs(0[],0)
    return res
}
Copy the code

2.4 Parenthesis GenerationForce buckle 22. Parenthesis generation

2.4.1 Problem Description

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations. Example 1:

Enter n =3Output:"((()))"."() () ()"."() () ()"."() () ()"."() () ()"]
Copy the code

Example 2:

Enter n =1Output:"()"]
Copy the code

2.4.2 Problem Analysis

This problem can be solved by using the stack, which I won’t show you here. So let’s do it the same way we do dynamic programming.

Horizontal for loop:

Every time weYou can choose either the open parenthesis or the close parenthesis

Vertical recursion:

Recursive termination condition where the length of the current parenthesis selection is equal to twice the target value (a pair of parentheses corresponds to n=1)

Photo source:Stupid pig blast team

2.4.3 the answer

var generateParenthesis = function(n) {
    const res = [] / / the result set
    // l indicates the number of options left in the open parenthesis, r indicates the close parenthesis; STR represents the result of the current selection
    const dfs = (l,r,str) = >{ 
        if(str.length==n*2){
            res.push(str)
            return
        }
        if(l>0) {// The left parentheses can be selected as long as they are left
            dfs(l-1,r,str+'(')}if(r>l){ Optional if the number of left parentheses is greater than the number of left parentheses
            dfs(l,r-1,str+') ')
        }
    }
    dfs(n,n,' ')
    return res
};
Copy the code

2.5 String ArrangementToe offer38. String alignment

2.5.1 Problem Description

Enter a string and print out all permutations of the characters in the string.

You can return this array of strings in any order, but no repeating elements.

Example:

Enter: s ="abc"Output:"abc"."acb"."bac"."bca"."cab"."cba" ] 
Copy the code

2.5.2 Problem Analysis

If you look closely at the above four problems, you’ll immediately think of backtracking when you get this one. Because it’s obviously an n-tree expansion. Horizontal for loop: Select elements

For the first time, you can select any element, and the following elements must be currentChoose the pathIt didn’t show up. For example,a->bAnd then you can’t choose EITHER A or B

Vertical recursion: Determine the termination conditions for recursion

Pass in num, which records the length of the path and terminates recursion when the length equals the length of the destination

2.5.3 answer

Version 1

var permutation = function(s) {
   const res = []
   const used = {}
   const dfs = (num,path) = >{
       if(num==s.length){
           res.push(path.join(' '))
           return
       }
       for(const c of s){
           if(used[c]){
               continue
           }
           used[c] = true
           path.push(c)
           dfs(num+1,path)
           used[c] = false
           path.pop()
       }
   }
   dfs(0[]),return res
};
Copy the code

Version 1 will look very similar to the full permutation we did before. But if the test case is AAC and it doesn’t pass, then we don’t mark the value, but instead, we mark the subscript.

Another problem with marking subscripts is repetition: again, taking aac as an example, subscripts 0,1,2 are the same as subscripts 1,0,2. So we also need to do a de-redo operation on the result.

var permutation = function(s) {
    const res = [] / / the result set
    const used = [] // Record the selection path subscript
    const dfs = (path) = >{
        if(path.length==s.length){ // Recursive termination condition
            res.push(path)
            return
        }
        for(let i=0; i<s.length; i++){if(used[i]) continue
            used[i] = true
            // Path is used as a string directly, so when the recursive stack finishes, it automatically backtracks
            dfs(path+s[i]) 
            used[i] = false
        }
    }
    dfs(' ')
    return [...new Set(res)]
}
Copy the code

2.6 Sum of Combinations IIForce buckle 40. Combination sum II

2.6.1 Problem Description

Given a set of numbered candidates and a target number, find all combinations of the candidates that can be summed as target.

Each number in the candidates must be used only once in each combination.

Note: The solution set cannot contain repeated combinations. Example 1:

Enter: candidates = [10.1.2.7.6.1.5], target = 8, output: [[1.1.6],
[1.2.5],
[1.7],
[2.6]]Copy the code

Example 2:

Enter: candidates = [2.5.2.1.2], target = 5, output: [[1.2.2],
[5]]Copy the code

2.6.2 Problem Analysis

Compared with the first version of the combined total, this version has the following main problems;

The candidate id candidates can be repeated
Each number can only be used once in each combination

For a simple example [1,1,7], target = 8 element subscript 0->2 is the same as element subscript 1->2. So, based on version 1, let’s sort the candidates first. Apply a constraint to the horizontal for loop to see if it is the same as the previous element, and skip if it is.

2.6.3 answer

var combinationSum2 = function(candidates, target) {
    const res = [] / / the result set
    const used = [] // Use subscripts to record paths
    candidates.sort((a,b) = >a-b) 
    // start-> record subscript sum-> current and path-> select path
    const dfs = (start,sum,path) = >{
        if(sum>=target){ // Recursive termination condition
            if(sum==target){ 
                res.push(path.slice())
            }
            return
        }
        // Horizontal for loop,start to avoid using the same element twice
        for(leti=start; i<candidates.length; i++){// Cut branches with different subscripts but the same result
            if(i! =0&&candidates[i]==candidates[i-1]&&used[i-1]) {continue
            }
            used[i] = true
            path.push(candidates[i])
            dfs(i+1,sum+candidates[i],path)
            path.pop() / / back
            used[i] = false
        }
    }
    dfs(0.0[]),return res
};
Copy the code

2.7 combinationForce buckle 77. Combination

2.7.1 Problem Description

Given two integers n and k, return all possible combinations of k numbers in the range [1, n].

You can return the answers in any order. Example 1:

Enter n =4, k = 2Output: [[2.4],
  [3.4],
  [2.3],
  [1.2],
  [1.3],
  [1.4]]Copy the code

Example 2:

Enter n =1, k = 1Output: [[1]]
Copy the code

2.7.2 Problem Analysis

Horizontal for loop:

You can pick anything from 1 minus n, but you can’tGo back toSo if you pick 3, you can’t pick 1 again, you can’t pick 3 again, so you don’t have to repeat the result. This can be solved by starting the subscript

Vertical recursion:

The recursive termination condition is: the length of the currently selected path is equal to k

2.7.3 the answer

In fact, I wrote it here, if the previous cases are knocked aside, this problem can actually come up with ideas in 2 minutes. Implementation is also not difficult.

var combine = function(n, k) {
    const res = [] // Process the result set
    // start record subscript path Record the selected path
    const dfs = (start,path) = >{
        if(path.length==k){ // Recursive termination condition
            res.push(path.slice())
            return
        }
        for(leti=start; i<=n; i++){ path.push(i) dfs(i+1,path)
            path.pop()
        }
    }
    dfs(1[]),return res
};
Copy the code

(iii) More backtracking:

257- All paths to a binary tree
【 medium 】17- a combination of letters for a telephone number
【 medium 】79- Word search
[Medium] 332- Reschedule

Increased difficulty:

Queen 51-N
[medium] 377- Sum of combinations ⅳ
【 medium 】60- the KTH rank

Even harder

[Difficulty] 37- Solving sudoku

4. Conclusion/conclusion

See here certainly is the classmate that loves study very much, right say is you 😜.Copy the code

We briefly summarize several characteristics of backtracking algorithm:

Backtracking algorithm is a continuous exhaustive (recursive) process, is a kind ofDon't look back until you hit the south wallIn the algorithm.
Many backtracking problems can be reduced to oneN fork treeThe termination condition of the recursion is determined vertically by horizontal (each selection of the for loop), which can often be written out quicklyThe framework.
If you don’t know anything, dodrawingYou mustdrawing🌍

Well this article is introduced here, if it is helpful to you, welcome to give me a point 👍, pay attention not to get lost, I am Shao Xiaobai, personal wechat: XpTZ15387507459, there are problems can communicate with you.

For you must be before | backtracking algorithm 】 【 ByteDance

Preface ✨

Experience sharing

(1) Backtracking to solve the problem ✨

1.1 Introduction to backtracking algorithm

1.2 Main problems solved by backtracking algorithm

1.3 Template of backtracking algorithm

(2) Examples of backtracking algorithm

2.1 all arrangementForce buckle 46. Full alignment

2.1.1 Problem Description

2.1.2 Problem analysis

2.1.3 the answer

2.2 Restoring the IP AddressRestore the IP address

2.2.1 Problem Description

2.2.2 Problem Analysis

Then the answer

2.3 Combination SumForce buckle 39. Sum of combinations

2.3.1 Problem Description

2.3.2 Problem Analysis

2.3.3 the answer

2.4 Parenthesis GenerationForce buckle 22. Parenthesis generation

2.4.1 Problem Description

2.4.2 Problem Analysis

2.4.3 the answer

2.5 String ArrangementToe offer38. String alignment

2.5.1 Problem Description

2.5.2 Problem Analysis

2.5.3 answer

2.6 Sum of Combinations IIForce buckle 40. Combination sum II

2.6.1 Problem Description

2.6.2 Problem Analysis

2.6.3 answer

2.7 combinationForce buckle 77. Combination

2.7.1 Problem Description

2.7.2 Problem Analysis

2.7.3 the answer

(iii) More backtracking:

4. Conclusion/conclusion

Related Posts

JQuery features overview

File upload is implemented in VUe3 through the Upload component of Element-Plus

Nuggets articles to watch this week (June 6-May 11)

For you must be before | backtracking algorithm 】【 ByteDance