Detailed explanation of retrospective thinking

backtracking , It can generally solve the following problems ：

• Combination question ：N Find out according to certain rules k A collection of numbers

• Cutting problem ： There are several ways to cut a string according to certain rules

• Subset problem ： One N How many subsets meet the condition in the set of numbers

• The problem of permutation ：N The numbers are arranged according to certain rules , There are several arrangements

• Chessboard problem ：N Queen , And so on

Because the backtracking method solves the recursive search of subsets in the set , The size of the set constitutes the width of the tree , The depth of recursion , The depth of the tree .

 

void backtracking( Parameters ) {
    if ( Termination conditions ) {
         Store results ;
        return;
    }

    for ( choice ： The elements in this layer set （ The number of children in a tree is the size of the set ）) {
         Processing nodes ;
        backtracking( route , Selection list ); //  recursive 
         to flash back , Cancel processing result 
    }
}

Retrospective trilogy

1 Return values and parameters of recursive functions

2  Termination condition of backtracking function

3  The process of single-layer search

Combination question ：N Find out according to certain rules k A collection of numbers

//  1.  Determine the solution space 
let result = []
let step = []
//2.  Determining parameters   n Traverse the number of child elements ,k Traversable depth 
function backTracing(n, k, startindex){
    //  2.  Determine the backtracking termination condition , Here is the array length , It is certain that there is a solution 
    if (step.length === k) {
         result.push(Array.from(step))
        return
    }
    for (let i = startindex; i <= n; i++) {
        // 3.  Determine the processing node 
        step.push(i)
        backTracing(n, k, i + 1)
        step.pop()
    }
}



var combine = function (n, k) {
     result = []
     step = []
    backTracing(n, k, 1)
    return result
};

The problem of permutation ：N The numbers are arranged according to certain rules , There are several arrangements

//  1.  Determine the solution space , Single layer solution and total solution 
let result = []
let step = []
let occupied = [0, 0, 0]
// 2.  Determine the parameters and return values of the backtrace function 
function backTracking( nums) {
    
    // 2.  Determine recursive termination conditions 
    if (step.length===nums.length ) {
        result.push(Array.from(step))
        return
    }
    for (let i = 0; i < nums.length; i++) {
        //  Determine the operation 
        if (occupied[i] === 0) {
            step.push(nums[i])
            occupied[i] = 1
            backTracking(nums)
            occupied[i] = 0
            step.pop()
        }
    }
}
var permute = function (nums) {
    backTracking( nums)

    console.log(result)
    
    return result
};

Subset problem ： One N How many subsets meet the condition in the set of numbers  

Similar to the combinatorial problem , But collect the answers at each node, not at the leaf node

//  1  Define the solution space 
let result = []
let step = []
// 2  Define the parameters and inverse values of the backtrace function 

function backTracing(startIndex, nums) {
    result.push(Array.from(step))
    // 3  Define termination conditions 
    if (startIndex === nums.length) {
        return
    }
    // // 4  Define operations , Traverse each element 

    for(let i=startIndex;i<nums.length;i++){
        step.push(nums[i])
        backTracing(++i, nums)
        step.pop()
    }
}
var subsets = function (nums) {
    result = []
    step = []
    backTracing(0, nums)
    console.log(result)
};
subsets([1, 2, 3])

Cutting problem ： There are several ways to cut a string according to certain rules  

How is this different from the combinatorial problem ?

Combinatorial problems with more conditional judgments

/**
 * @param {string} s
 * @return {string[][]}
 */
//  1  Solution space 
let result = []
let step = []
//2  The parameters and return values of the backtrace function 
//split[] Cut point array , Tree width .count Number of cutting points , Tree depth 
function backTracing(starIndex, s) {
    //3  Termination conditions 
    if (starIndex == s.length) {
        result.push(Array.from(step))
        return
    }
    for (let i = starIndex; i < s.length; i++) {
        if (isPalindrome(s, starIndex, i)) {   //  It's a palindrome string 
            //  obtain [startIndex,i] stay s The substring in 
            const str = s.substr(starIndex, i - starIndex + 1);
            step.push(str);
        } else {                                //  Not a palindrome , skip 
            continue;
        }
        backTracing(i+1, s)
        step.pop()
    }
}
function isPalindrome(s, start, end) {
    for (let i = start, j = end; i < j; i++, j--) {
        if (s[i] != s[j]) {
            return false;
        }
    }
    return true;
}
var partition = function (s) {
    result=[]
    step=[]
    backTracing(0, s)
    return result
};

Personal summary :

The backtracking algorithm is not very difficult , There are mainly two

1. Take each node as the type of result set ( Subset problem )
2. Take the leaf node as the type of result set ( The problem of permutation , Combination question , Cutting problem )