Backtracking algorithm, there are many kinds of algorithm questions in Leetcode, combined with a few Leecode questions, deepen the understanding of this, convenient to brush questions happily in the future.

Backtracking algorithm

concept

Backtracking, or DFS, when you see depth-first, what do you think? Is the tree traversal, one path to black, and then back to the previous step, is a tentative algorithm. And the way to do it, let me just say it, is recursively.

sample

To illustrate:

Leetcode Restores the iP address

Given a string containing only numbers, undo it and return all possible IP address formats. IP addresses have the following characteristics:

  • 4 integers (each integer between 0 and 255)
  • You can’t start with zero, but you can have one zero
  • Integers are separated by ‘.’

So let me just draw a tree diagram of it, and usually when I do backtracking, I just draw a graph.

It can be seen that the backtracking algorithm is actually a depth-first search attempt process similar to enumeration, which is mainly to find the solution of the problem during the search attempt. When it is found that the solution condition is not met, it will “backtrack” back (that is, recursive return) and try other paths.

The problem solving

As mentioned earlier, since the backtracking algorithm uses recursion, LET me use recursion to solve this problem:

var restoreIpAddresses = function(s) {
    let res = [];
    dfs(s, 1, -1[]);/** * backtracking algorithm *@param {*} The string * passed in by STR@param {*} Level Indicates the number of an IP address. The value starts from 0 *@param {*} Index The position of the string to be selected *@param {*} IpAddress Indicates the IP address. The value is entered as an array. Connect. For example, [192, 168, 80, 1] can be connected to 192.168.80.1 */
    function dfs(str, level, index, ipAddress) {
        //1. Cut-off conditions
        if(level === 5 || index === str.length -1) {if(level === 5 && index === str.length -1){
                res.push(ipAddress.join('. '));
            }           
            return;
        }
        
        // 2. Candidate node
         // Each integer is between 0 and 255, with the first three digits at most
         for(let i =1; i <4; i++){
           let ip = str.substr(index+1, i);

            // Check whether conditions ranging from 0 to 255 are met. The value cannot start with 0
           if(parseInt(ip)<256 && ( ip === '0'| |! ip.startsWith('0'))){
                ipAddress.push(ip);
                dfs(str,level+1,index+i,ipAddress); ipAddress.pop(); }}}return res;
}
Copy the code

The problem solving template

  • Determine the recursive termination condition
  • Find the candidate node to push
  • Pop out the data after completing the recursion, called backtracking

This is just a template for how I think to solve this kind of problem.

Backtracking problem solving

The main brush a few leecode topic to deepen their understanding, are set above the template

A combination of letters for a telephone number

Telephone number alphabetic combination 

/ * * *@param {string} digits
 * @return {string[]}* /
var letterCombinations = function(digits) {
    // Handle boundary conditions
    if(digits.length<1) {return[]}let res=[];
   

    // Create a map data structure to store numbers and letters
    let map = new Map()
        .set('2'.'abc')
        .set('3'.'def')
        .set('4'.'ghi')
        .set('5'.'jkl')
        .set('6'.'mno')
        .set('7'.'pqrs')
        .set('8'.'tuv')
        .set('9'.'wxyz');

     dfs(digits, 0 , ' '); 
   
   /** * digits: string passed in * index: number traversed * STR: combination of letters */
    function dfs(digits, index, str){
        //1. Cut-off conditions
        if(index === digits.length){
            res.push(str);
            return;
        }
        // 2. Candidate node
        for(let s of map.get(digits[index])){
            str+= s;
            dfs(digits, index+1,str);
            // 3. Backtrace, pop from stack
            str= str.slice(0, str.length-1); }}return res;
};
Copy the code

The total number of combinations

The total number of combinations 

/ * * *@param {number[]} candidates
 * @param {number} target
 * @return {number[][]}* /
var combinationSum = function(candidates, target) {
    let res = [];
    let strArr = [];
    dfs(candidates, target, []);

    function dfs(candidates, remain, arr){
        if(remain <= 0) {if(remain === 0) {let str = [...arr].sort(function(a,b) {
                    return a-b;
                });
                // This is mainly about de-weighting
                if(strArr.indexOf([...str].toString()) === -1){ strArr.push([...str].toString()); res.push([...str]); }}return;
        }
        for(let can ofcandidates){ remain -= can; arr.push(can); dfs(candidates, remain, arr); remain+=can; arr.pop(); }}return res;
};
Copy the code